题解 P1583 【魔法照片】

· · 题解

这道题真的很绕……我交了四五次才最终AC。

题目实际上指的是先给定你1~n号对应的权值，从大到小排序后根据当前次序再编第二次号，分类别加上对应的e[i]，再次从大到小进行排序后输出前k大权值分别的初始编号。

注意！第二次编号与最终的编号输出无关，仅用于分类。

举个例子：

输入：（测试点#1）

14 3 9 2 5 4 0 0 0 0 0 0

1 1 3 4 9 2 8 2 8 8 8 7 1 9

编号为：1 2 3 4 5 6 7 8 9 10 11 12 13 14

第一次排序后：（序号小优先）

9 9 8 8 8 8 7 4 3 2 2 1 1 1

编号为：5 14 7 9 10 11 12 4 3 6 8 1 2 13

类别为：1 2 3 4 5 6 7 8 9 10 1 2 3 4

加上e[i]后：18 11 13 12 8 8 7 4 3 2 11 3 6 5

第二次排序后：（序号小优先）

18 13 12 11 11 8 8 7 6 5 4 3 3 2

编号为：5 7 9 8 14 10 11 12 2 13 4 1 3

输出：5 7 9

这就是这道题大概的思路：输入——排号——排序——分类加e[i]——排序——输出

如果对上面的推导过程有什么疑问，可以自己动手尝试。

最后附上代码，希望能帮到大家(｀・ω・´)：

#include<cstdio>
#include<algorithm>
using namespace std;
int e[12],n,k;
struct person{
    int w;//权值 
    int num;//编号 
    int d;//类别 
}p[20010];//储存每个人的信息 
int w_comp(const person &a,const person &b){
    if(a.w!=b.w)return a.w>b.w;//从大到小排序 
    return a.num<b.num;//序号小优先 
}//结构体排序 
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<10;i++)scanf("%d",&e[i]);
    for(int i=0;i<n;i++){
        scanf("%d",&p[i].w);
        p[i].num=i+1;
    }//读入+编号 
    sort(p,p+n,w_comp);//第一次排序 
    for(int i=0;i<n;i++){
        p[i].d=i%10;//分类 
        p[i].w+=e[p[i].d];//加上e[i] 
    }
    sort(p,p+n,w_comp);//第二次排序 
    for(int i=0;i<k;i++)printf("%d ",p[i].num);
}