又到了收獲的季節(jié)，樹上結(jié)了許多韜韜，錯(cuò)了，是許多蘋果，有很多個(gè)小韜韜都來摘蘋果。每個(gè)韜韜都想要最大的蘋果，所以發(fā)生了爭(zhēng)執(zhí)，為了解決他們的矛盾，出題人定了一項(xiàng)特殊的規(guī)則，按體重的大小來定順序，每一輪都是先由胖的先摘（照顧胖子），每個(gè)韜韜都是很聰明的，不會(huì)錯(cuò)過眼前最大的蘋果?，F(xiàn)在問題來了，一共有n個(gè)蘋果，m個(gè)韜韜，要你按原順序輸出每個(gè)韜韜可以搶到的蘋果的總大小。

Input

第一行兩個(gè)數(shù)n,m。

接下來一行n個(gè)數(shù)，分別為每個(gè)蘋果的大小。

接下來一行m個(gè)數(shù)，分別為每個(gè)韜韜的體重。

Output

一行m個(gè)數(shù)，每個(gè)韜韜搶到的蘋果的大小。

Sample Input

5 3

1 2 3 4 5

1 2 3

Sample Output

3 5 7

[數(shù)據(jù)規(guī)模]

n,m<=100000

思路

這一題,乍一看題目,"啊_好水啊".可是嘞......

雖然看起來很水,但不過我寫的代碼比"韜韜摘蘋果"的多了去了.先說咋做吧.

1.輸入

輸入就不用說了,但是這里面需要把"肥韜韜"走一個(gè)結(jié)構(gòu)體,輸入的代碼如下

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;//記錄編號(hào)
}

2.排序

題目表述的非常的清楚,我們要將韜韜按肥瘦排序,因?yàn)?00000不算大,sort過一遍即可.

int cmp(node a, node b)//按重量關(guān)鍵字排序
{
    return a.w > b.w;//大到小
}
{
...//其他代碼
}
sort(t + 1, t + m + 1, cmp);//這是排序的函數(shù)
sort(apple + 1, apple + 1 + n);//蘋果也順便π下

3.存答案

這一步也十分的牛13,額.

首先將蘋果從n到1過一遍,然后韜韜按照之前預(yù)處理好的宅蘋果.

int k = n;//k枚舉apple
int i = 1;//i枚舉韜韜
while(k != 0)
{
    t[i].c += apple[k];//記錄累加
    k--;//蘋果被宅
    i++;//掄到下一個(gè)韜韜
    if(i > m)//掄玩一遍
        i = 1;//再輪一遍
}

4.輸出

輸出就美麗啦,但是他是按編號(hào)輸出的,現(xiàn)在的復(fù)雜度有點(diǎn)堪憂,算啦,管他,再拍一遍.

int cmp2(node a, node b)
{
    return a.l < b.l;//按編號(hào)排
}
{
    ...//其他
}
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);
    }
}