商品纪念铺 - 题解
2023-08-08 22:48:19
发布于：浙江
前言
又到了万众瞩目的我Macw来给大家讲题。感谢x01班的同学们参与本场oi考试，oi赛制的考试确实比ioi赛制的考试要刺激（老师们也感到刺激）。今天的题目一共七道题，难度确实也稍微有点大，但我为你们x01班的所有同学鼓掌，为你们的坚持喝彩。
题目解析 - 商品纪念铺
题目链接：https://www.acgo.cn/problemset/4441/info?teamCode=1664181761155715072。
这道题考查的核心知识点在于同学对数组等线性表的”增删改差“操作。数组是一个很神奇的数据结构，其在内存中是连续分布的，因此对数组来说，删除元素是一个很复杂的事情。虽然本题难度比较大，但可以将一个大问题分解为许多个小问题一一解决，这样子这道题就很好做出来了。
问题一：如何进行数组的初始化操作？
这一个小问题考察的就是学生在数组中存储数据的熟练程度。数组的存储可以使用一个for循环批量的将数据存储下来：
int n, arr[10005] = {};
cin >> n;
for (int i=1; i<=n; i++){
cin >> arr[i];
}
这就完成了第一步操作，是不是非常简单？
问题二：如何进行数组的单点累加操作？
所谓的数组单点累加操作，就是取数组中的m个数，将这m个数相加即可。这个小问题考察的就是学生对数组索引取值的掌握程度。为了获取数组中某一个位置上的值，可以通过索引获得。
例如获取数组中的第一个数字：
int arr[105] = {0, 1, 3, 5, 7};
cout << arr[1] << endl;
因此，我们可以创建一个累加器total，用于记录所有数字的和。代码如下，其中n代表需要累加的数字的数量，t代表每一个累加的数字的索引。
int n, total = 0;
cin >> n;
for (int i=1; i<=n; i++){
int t;
cin >> t;
total += arr[t];
}
先献上本题的前半部分的代码，到目前为止应该都是很简单的，就是普通的数组操作仅此而已。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
// n代表一开始商店里有n个商品。
// m代表来了m位顾客。
cin >> n >> m;
// 定义数组arr，arr[i]表示第i个商品的价格。
int arr[5010]={0};
// 读入每一个商品的价格。索引从1开始。
for(int i=1;i<=n;i++) cin>>arr[i];
// 循环遍历m次，对每次顾客的请求都做模拟操作。
for(int l=1;l<=m;l++){
// 读入k，k表示顾客需要购买的商品数量为k。
int k; cin>>k;
// 定义total，total用于记录这k个商品累加后的值。
int total=0;
// 循环k次，读入这k个商品的索引。
for(int i=1;i<=k;i++){
int a; cin>>a;
// 并将这k个商品的价格累计到total中。
total+=arr[a];
}
cout<<total<<" "; // 输出结果。
/*
对数组进行重新排序操作。
*/
}
return 0;
}
接下来难度就要上去了，有请：
问题三：如何将数组的数往前挪一位？
这个问题也比较简单，可以通过一层for循环的方式解决。具体代码如下：
int arr[105] = {0, -1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (int i=1; i<=9; i++){
arr[i] = arr[i+1];
}
以上代码应该非常好理解，将数组中第i+1个位置的数存到数组中的第i个位置。这样子就能完成将数组中的数往前挪一位的效果。这就是本题的核心难度，本题最难的地方就是如何将数组中所有的数字往前挪一位，如果到这里你都看得懂的话，那么恭喜你这道题对你来说就是小菜一碟了。
问题四：在什么时候需要将数组中的数往前挪一位？
这个问题也很好理解。设想一下在数组中，如果这个数已经被取走了，则后面的数字都需要在数组中往前挪一位。因此问题就被转化成了如何记录一个数字已经被取走了？
事实上，我们可以在每次结束累加arr[i]的操作后将arr[i]的值设置为-1，这样子我们就可以通过遍历arr中的所有值的值哪些数字之后的数字都需要往前挪一位。
前半部分的代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
int arr[5010]={0};
for(int i=1;i<=n;i++) cin>>arr[i];
for(int l=1;l<=m;l++){
int k; cin>>k;
int total=0;
for(int i=1;i<=k;i++){
int a; cin>>a;
total+=arr[a];
// 将这个商品的价格赋值为-1，代表这个商品已经被人取走了。
arr[a] = -1;
}
cout<<total<<" ";
/*
对数组进行重新排序操作。
*/
}
return 0;
}
问题五：当取走k物品后，数组的长度是多少？
一开始，数组的长度为n，代表有n件商品。随着商品被购买走后，n的大小也需要随之减少。那当k件商品被取走了，n的大小是多少呢？答案是n的大小会缩小k，也就是n -= k。也就是说，每次当一个物品被买走后，数组在排序后的长度就是原本长度-1。这个应该很好理解吧。
最后，完整代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
// n代表一开始商店里有n个商品。
// m代表来了m位顾客。
cin >> n >> m;
// 定义数组arr，arr[i]表示第i个商品的价格。
int arr[5010]={0};
// 读入每一个商品的价格。索引从1开始。
for(int i=1;i<=n;i++) cin>>arr[i];
// 循环遍历m次，对每次顾客的请求都做模拟操作。
for(int l=1;l<=m;l++){
// 读入k，k表示顾客需要购买的商品数量为k。
int k; cin>>k;
// 定义total，total用于记录这k个商品累加后的值。
int total=0;
// 循环k次，读入这k个商品的索引。
for(int i=1;i<=k;i++){
int a; cin>>a;
// 并将这k个商品的价格累计到total中。
total+=arr[a];
}
cout<<total<<" "; // 输出结果。
// 再次遍历每一个位置，查看这个位置原本的商品是否被购买走了。
/* 根据之前所说的，如果这件商品被购买走的话，
就需要将前面所有的商品都往前挪一位。*/
for(int i=1;i<=n;i++){
// 如果这个商品被买走了。
while(arr[i]==-1){
// 将后面的数字往前挪。
for(int j=i;j<n;j++){
arr[j]=arr[j+1];
}
// n--的意思就是说这数组的数每往前挪一位，
// 数组的长度就是原本长度-1。
n--;
}
}
}
return 0;
}
上面这个代码是肖老师的代码，肖老师的代码比较好理解，这边再附上我自己写的官方版本，稍微有点难理解，但是总体的思路都是差不多的。
#include <iostream>
using namespace std;
int n, k, m;
int arr[5050];
int main(){
cin >> n >> k;
for (int i=1; i<=n; i++){
cin >> arr[i];
}
while(k--){
cin >> m;
// 计算总价。
int total = 0, t;
for (int i=1; i<=m; i++){
cin >> t;
total += arr[t];
arr[t] = -1;
}
cout << total << " ";
// 重新排序。
int left = 1;
int right = 1;
while(left <= n - m){
if (arr[left] != -1) left++;
else{
right = left;
while(right <= n && arr[right] == -1) right++;
arr[left] = arr[right];
arr[right] = -1;
left++; right++;
}
}
n -= m;
}
return 0;
}
小彩蛋
在赛后看题目的过程中，我还看到了x01同学给我献上的真挚祝福（大家都挺开心的）。
/*
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||- \
| | \\\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
`-.____`-.___\_____/___.-`____.-'
//我佛慈悲，超度我吧！！！精神超度不了，就物理超度！！！
//我佛慈悲，超度我吧！！！精神超度不了，就物理超度！！！
//我佛慈悲，超度我吧！！！精神超度不了，就物理超度！！！
//我佛慈悲，超度我吧！！！精神超度不了，就物理超度！！！
//我佛慈悲，超度我吧！！！精神超度不了，就物理超度！！！
.....
*/
极限辣！
#include<bits/stdc++.h>
using namespace std;
int n[114514];
int main() {
freopen("kai.in","r",stdin);
freopen("kai.out","w",stdout);
cout<<"HGF II JJJ DEEDC";
//哎呦我*&*^&^*^^,真的是$*&^*^&%$^%
//真的,我&^$%&^%*^
//真^%*^%#^&^%%不是人啊
//我祝作者 身体健康,万事如意,早生贵子,寿比昙花
fclose(stdin);
fclose(stdout);
return 0;
}
好了，今天就到此为止吧，祝大家在杭州过得开心，过得快乐！
全部评论 14
你出的题不是人出的！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
2023-08-21 来自 四川
0你一定要痛苦下一界╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)╭╮(╯-╰)
2023-08-21 来自 四川
0
有帮助，赞一个