又到了收获的季节，树上结了许多韬韬，错了，是许多苹果，有很多个小韬韬都来摘苹果。每个韬韬都想要最大的苹果，所以发生了争执，为了解决他们的矛盾，出题人定了一项特殊的规则，按体重的大小来定顺序，每一轮都是先由胖的先摘（照顾胖子），每个韬韬都是很聪明的，不会错过眼前最大的苹果。现在问题来了，一共有n个苹果，m个韬韬，要你按原顺序输出每个韬韬可以抢到的苹果的总大小。
Input
第一行两个数n,m。
接下来一行n个数，分别为每个苹果的大小。
接下来一行m个数，分别为每个韬韬的体重。
Output
一行m个数，每个韬韬抢到的苹果的大小。
Sample Input
5 3
1 2 3 4 5
1 2 3
Sample Output
3 5 7
[数据规模]
n,m<=100000
思路
这一题,乍一看题目,"啊好水啊".可是嘞......
虽然看起来很水,但不过我写的代码比"韬韬摘苹果"的多了去了.先说咋做吧.
1.输入
输入就不用说了,但是这里面需要把"肥韬韬"走一个结构体,输入的代码如下
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &apple[i]);//苹果
for(int i = 1; i <= m; i++)
{
scanf("%d", &t[i].w);//输入韬韬的重量
t[i].l = i;//记录编号
}
2.排序
题目表述的非常的清楚,我们要将韬韬按肥瘦排序,因为100000不算大,sort过一遍即可.
int cmp(node a, node b)//按重量关键字排序
{
return a.w > b.w;//大到小
}
{
...//其他代码
}
sort(t + 1, t + m + 1, cmp);//这是排序的函数
sort(apple + 1, apple + 1 + n);//苹果也顺便π下
3.存答案
这一步也十分的牛13,额.
首先将苹果从n到1过一遍,然后韬韬按照之前预处理好的宅苹果.
int k = n;//k枚举apple
int i = 1;//i枚举韬韬
while(k != 0)
{
t[i].c += apple[k];//记录累加
k--;//苹果被宅
i++;//抡到下一个韬韬
if(i > m)//抡玩一遍
i = 1;//再轮一遍
}
4.输出
输出就美丽啦,但是他是按编号输出的,现在的复杂度有点堪忧,算啦,管他,再拍一遍.
int cmp2(node a, node b)
{
return a.l < b.l;//按编号排
}
{
...//其他
}
sort(t + 1, t + m + 1, cmp2);
for(i = 1; i <= m; i++)
{
printf("%d ", t[i].c);//拍完后输出
}
噜噜噜,这题就解决了,贴整体代码:
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m;
int apple[100001];
struct node {
int l;
int w;
int c;
}t[100001];
int cmp(node a, node b)
{
return a.w > b.w;
}
int cmp2(node a, node b)
{
return a.l < b.l;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &apple[i]);
for(int i = 1; i <= m; i++)
{
scanf("%d", &t[i].w);
t[i].l = i;
}
sort(t + 1, t + m + 1, cmp);
sort(apple + 1, apple + 1 + n);
int k = n;
int i = 1;
while(k != 0)
{
t[i].c += apple[k];
k--;
i++;
if(i > m)
i = 1;
}
sort(t + 1, t + m + 1, cmp2);
for(i = 1; i <= m; i++)
{
printf("%d ", t[i].c);
}
}
