题目链接: https://www.luogu.org/problemnew/show/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]从高到低的人的编号.
输入输出样例
输入样例 #1:
- 10 10
- 1 2 3 4 5 6 7 8 9 10
- 2 4 6 8 10 12 14 16 18 20
输出样例 #1:
10 9 8 7 6 5 4 3 2 1
题解:
我们可以根据 $W[i]$ 对 $n$ 个人的编号进行排序, 然后就能 $O(n)$ 的把每个人对应的额外值 $E[i]$ 其身上.
然后再做一遍根据新的 $W[i]$ 对 $n$ 个人的编号进行排序, 然后输出即可.
AC 代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=2e4+10;
- int n,k;
- int e[13];
- int w[maxn],d[maxn];
- bool cmp(int a,int b) {
- return (w[a]==w[b])?(a<b):(w[a]>w[b]);
- }
- int main()
- {
- cin>>n>>k;
- for(int i=1;i<=10;i++) cin>>e[i];
- for(int i=1;i<=n;i++) cin>>w[i], d[i]=i;
- sort(d+1,d+n+1,cmp);
- for(int i=1;i<=n;i++) w[d[i]]+=e[(i-1)%10+1];
- for(int i=1;i<=n;i++) d[i]=i;
- sort(d+1,d+n+1,cmp);
- for(int i=1;i<=k;i++) cout<<d[i]<<((i==n)?'\n':' ');
- }
来源: http://www.bubuko.com/infodetail-2915713.html