洛谷 P1583 魔法照片

链接

https://www.luogu.org/problem/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

思路

排序，直接想到sort，每个对象多个元素，想起结构体，成了。

结构体中设置num表示初始序号，w表示权值，d表示取模后的值（不要也可以）；sort函数优先权值排序，其次序号排序，输入，排序，更新，排序，输出，行了。

（好像前几天才做过同类型的题目）

代码

#include<iostream>
#include<algorithm>

using namespace std;

struct peo
{
	int num;
	int w;
	int d;
}p[20001];

bool cmp(peo a,peo b)
{
	if(a.w!=b.w)
		return a.w>b.w;
	else 
		return a.num<b.num;
}

int main()
{
	int n,k;
	cin>>n>>k;
	int e[11];
	for(int i=1;i<11;i++)
	{
		cin>>e[i];
	} 
	for(int i=0;i<n;i++)
	{
		cin>>p[i].w;
		p[i].num=i+1;
	} 
	
	sort(p,p+n,cmp);

	for(int i=0;i<n;i++)
	{
		p[i].d = i%10+1;
		p[i].w += e[p[i].d];
	} 

	sort(p,p+n,cmp);
	for(int i=0;i<k;i++)
	{
		cout<<p[i].num<<" ";
	} 
}