佳佳的魔法照片
Description
【題目背景】
如果你看過《哈利?波特》，你就會知道魔法世界里的照片是很神奇的。也許是因為小魔法師佳佳長的太帥，很多人都找他要那種神奇的魔法照片，而且還都要佳佳和他的MM的合照。那些照片可是非常珍貴的，他到底應(yīng)該把照片給誰呢？
一共有n個人（以1–n編號）向佳佳要照片，而佳佳只能把照片給其中的k個人。佳佳按照與他們的關(guān)系好壞的程度給每個人賦予了一個初始權(quán)值W[i]。然后將初始權(quán)值從大到小進(jìn)行排序，每人就有了一個序號D[i]（取值同樣是1–n）。按照這個序號對10取模的值將這些人分為10類。也就是說定義每個人的類別序號C[i]的值為(D[i]-1) mod 10 +1，顯然類別序號的取值為1–10。第i類的人將會額外得到E[i]的權(quán)值。你需要做的就是求出加上額外權(quán)值以后，最終的權(quán)值最大的k個人，并輸出他們的編號。在排序中，如果兩人的W[i]相同，編號小的優(yōu)先。
Input
第一行輸出用空格隔開的兩個整數(shù)，分別是n和k。
第二行給出了10個正整數(shù)，分別是E[1]到E[10]。
第三行給出了n個正整數(shù)，第i個數(shù)表示編號為i的人的權(quán)值W[i]。
Output
只需輸出一行用空格隔開的k個整數(shù)，分別表示最終的W[i]從高到低的人的編號。
Sample Input
10 10
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
Sample Output
10 9 8 7 6 5 4 3 2 1
Hint
對于50%的數(shù)據(jù)，n<=200；
對于100%的數(shù)據(jù)，n<=50 000，k<=2000，給出的所有正整數(shù)都不超過32767。
程序：
var n,k,i:longint; e:array[1..10]of longint; a:array[0..50000,1..4]of longint; procedure kp(l,r:longint); var i,j,mid,key1,key2:longint; beginif l>r then exit;mid:=l+random(r-l+1);key1:=a[mid,2];key2:=a[mid,1];i:=l;j:=r;repeatwhile (a[i,2]>key1) or (a[i,2]=key1) and (a[i,1]<key2) do inc(i);while (a[j,2]<key1) or (a[j,2]=key1) and (a[j,1]>key2) do dec(j);if i<=j thenbegina[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];inc(i); dec(j);end;until(i>j);kp(l,j);kp(i,r); end;beginreadln(n,k);for i:=1 to 10 doread(e[i]);readln;for i:=1 to n dobeginread(a[i,2]);a[i,1]:=i;end;kp(1,n);for i:=1 to n doa[i,3]:=i;for i:=1 to n doa[i,4]:=(a[i,3]-1) mod 10 +1;for i:=1 to n doa[i,2]:=a[i,2]+e[a[i,4]];kp(1,n);for i:=1 to k-1 dowrite(a[i,1],' ');if k<>0 then write(a[k,1]); end.轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9500056.html
總結(jié)
