P1583 魔法照片——题解

解题思路

用结构体保存编号和当前权值。第一次按“权值降序、编号升序”排序，排序下标 $i$ 对应类别 $i\bmod10$，加上相应额外权值；第二次使用同一比较规则排序，输出前 $k$ 个编号。

复杂度分析

两次排序，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
struct Person{int id,w;};
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,k;cin>>n>>k;
    int e[10];for(int i=0;i<10;i++) cin>>e[i];
    vector<Person>a(n);
    for(int i=0;i<n;i++){cin>>a[i].w;a[i].id=i+1;}
    auto cmp=[](const Person&A,const Person&B){return A.w!=B.w?A.w>B.w:A.id<B.id;};
    sort(a.begin(),a.end(),cmp);
    for(int i=0;i<n;i++) a[i].w+=e[i%10];
    sort(a.begin(),a.end(),cmp);
    for(int i=0;i<k;i++) cout<<a[i].id<<(i+1==k?'\n':' ');
    return 0;
}

#include <bits/stdc++.h> using namespace std; struct Person{int id,w;}; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n,k;cin>>n>>k; int e[10];for(int i=0;i<10;i++) cin>>e[i]; vectora(n); for(int i=0;i<n;i++){cin>>a[i].w;a[i].id=i+1;} auto cmp=[](const Person&A,const Person&B){return A.w!=B.w?A.w>B.w:A.id<B.id;}; sort(a.begin(),a.end(),cmp); for(int i=0;i<n;i++) a[i].w+=e[i%10]; sort(a.begin(),a.end(),cmp); for(int i=0;i<k;i++) cout<<a[i].id<<(i+1==k?'\n':' '); return 0; }