P1583 魔法照片

題目描述

一共有n（n≤20000）個人（以1--n編號）向佳佳要照片，而佳佳只能把照片給其中的k個人。佳佳按照與他們的關係好壞的程度給每個人賦予了一個初始權值W[i]。然後將初始權值從大到小進行排序，每人就有了一個序號D[i]（取值同樣是1--n）。按照這個序號對10取模的值將這些人分為10類。也就是說定義每個人的類別序號C[i]的值為(D[i]-1) mod 10 +1，顯然類別序號的取值為1--10。第i類的人將會額外得到E[i]的權值。你需要做的就是求出加上額外權值以後，最終的權值最大的k個人，並輸出他們的編號。在排序中，如果兩人的W[i]相同，編號小的優先。

輸入輸出格式

第一行輸入用空格隔開的兩個整數，分別是n和k。

第二行給出了10個正整數，分別是E[1]到E[10]。

第三行給出了n個正整數，第i個數表示編號為i的人的權值W[i]。

只需輸出一行用空格隔開的k個整數，分別表示最終的W[i]從高到低的人的編號。

輸入輸出樣例

10 10
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20

10 9 8 7 6 5 4 3 2 1

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int E[11];
 8 struct node
 9 {
10     int cs;//初始 
11     int xh;//序號
12     int bh;//編號 
13     int lbxh;// 類別序號 
14 }a[500001]; 
15 int comp(const node & a ,const node & b)
16 {
17     if(a.cs!=b.cs)
18     return a.cs>b.cs;
19     else
20     return a.bh<b.bh;
21 }
22 int main()
23 {
24     int n,k;
25     scanf("%d%d",&n,&k);
26     for(int i=1;i<=10;i++)
27         scanf("%d",&E[i]);
28     for(int i=1;i<=n;i++)
29         scanf("%d",&a[i].cs),a[i].bh=i;
30     sort(a+1,a+n+1,comp);
31     
32     for(int i=1;i<=n;i++)
33         a[i].xh=i;
34     
35     for(int i=1;i<=n;i++)
36         a[i].cs+=E[(a[i].xh-1)%10+1];
37         
38     sort(a+1,a+n+1,comp);
39     for(int i=1;i<=k;i++)
40         printf("%d ",a[i].bh);
41     return 0;
42 }