menu Error0 Blog
P1583 魔法照片
49 浏览 | 2019-11-13 | 分类:算法 | 标签:

题目描述

一共有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

代码

#include<iostream>
#include <iostream>
#include<algorithm>
using namespace std;
struct person {
    int d; /*序号*/
    int w; /*权值*/
    int c;/*分类*/
} ;

/*权值相同 优先取序号小的*/
bool cmp(person a, person b)
{
    if (a.w == b.w)
    {
        return a.d < b.d;
    }
    else return a.w > b.w;
}
person p[20001];
int e[10] = { 0 };

int main() {

    int n,  k;
    cin >> n >> k;
    for (int i =0; i <10; i++)
    {
        cin>>e[i];
    }
    for (int i = 0; i <n; i++)
    {
        cin >> p[i].w;
        p[i].d = i + 1;
    }
    sort(p, p + n,cmp);
    for (int i = 0; i < n; i++)
    {
        /*分类 加上额外权值*/
        p[i].c = i%10; 
        p[i].w += e[p[i].c];
    }
    sort(p, p + n, cmp);
    for (int i = 0; i <k; i++)
        cout << (p[i].d)<<" ";
    return 0;
}
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!

Emoji

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 46

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 48

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 87

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 89