韬韬抢苹果 #普及组#

又到了收获的季节，树上结了许多韬韬，错了，是许多苹果，有很多个小韬韬都来摘苹果。每个韬韬都想要最大的苹果，所以发生了争执，为了解决他们的矛盾，出题人定了一项特殊的规则，按体重的大小来定顺序，每一轮都是先由胖的先摘（照顾胖子），每个韬韬都是很聪明的，不会错过眼前最大的苹果。现在问题来了，一共有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);
    }
}