P1586 魔法照片

2019-11-14 10:12:50

字体：大中小

来源：转载

供稿：网友

题目描述

佳佳在n个人中把照片给k个人，关系好坏的程度为W[i]。按照从大到小的序号对10取模的值将这些人分为10类。求出加上额外权值以后，最终的权值最大的k个人，并输出他们的编号。如果两人的W[i]相同，编号小的优先。

样例输入

10 101 2 3 4 5 6 7 8 9 102 4 6 8 10 12 14 16 18 20

样例输出

10 9 8 7 6 5 4 3 2 1

思路

O(n log n) 模拟，排序；

var n,k,i:longint; a,b,c:array[0..30000] of longint;PRocedure qsort(l,r:longint);var p,t,m,j:longint;begin i:=l;j:=r; p:=a[(l+r) div 2]; m:=c[(l+r) div 2]; repeat while (a[i]>p)or((a[i]=p)and(c[i]<m)) do inc(i); while (a[j]<p)or((a[j]=p)and(c[j]>m)) do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; t:=c[i];c[i]:=c[j];c[j]:=t; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j);end;procedure init;begin readln(n,k); for i:=1 to 10 do read(b[i]); for i:=1 to n do read(a[i]);end;begin init; for i:=1 to n do c[i]:=i; qsort(1,n); for i:=1 to n do a[i]:=a[i]+b[(i-1) mod 10+1]; qsort(1,n); for i:=1 to k do write(c[i],' ');end.

上一篇：Validation校验（一）

下一篇：588A. Duff and Meat