【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e826
【解題想法】多鍵值排序
- gift[i]: 讀入資料時存放第 i 名粉絲的 (粉絲編號，贈禮金額)。一位粉絲可能有多筆贈禮，需累加贈禮金額。
- 全部資料讀取完畢後，進行排序，先針對贈禮金額由大排到小，金額相同的話，再針對粉絲編號由小排到大。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100005;
#define pii pair<int,int>
#define F first
#define S second
pii gift[maxn];
bool cmp(pii a, pii b){
if (a.S != b.S) return a.S > b.S;
else return a.F < b.F;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, M, n, X;
while (cin >> N >> M){
for (int i=0; i<N; i++){
gift[i].F = i;
gift[i].S = 0;
}
for (int i=0; i<M; i++){
cin >> n >> X;
gift[n].S += X;
}
sort(gift, gift+N, cmp);
for (int i=0; i<N; i++){
cout << gift[i].F << " " << gift[i].S << "\n";
}
}
}
Python code (credit: Amy Chou)
- 多鍵值排序：gift.sort ( key = lambda x: ( – x[1], x[0] ) )
- 本題讀入測資行數很多，0<=M<=10^6，要加上IO優化，避免TLE。【筆記】
- 本題毋須靠 EOF 停止程式，使用 readlines( ) 一次把所有測資讀進 list，會比使用迴圈一行一行用 readline( ) 讀入測資快上一些。
- 【做法1】使用 readline( )：1.8s
- 【做法2】使用 readlines( )：1.7s
# sys.stdin.readline()
# 1.8s
import sys
for line in sys.stdin:
N, M = map(int, line.split())
gift = [[i, 0] for i in range(N)]
for _ in range(M):
n, X = map(int, sys.stdin.readline().split())
gift[n][1] += X
gift.sort(key=lambda x:(-x[1], x[0]))
for n, X in gift:
print(n, X)
# sys.stdin.readlines()
# 1.7s
import sys
lines = sys.stdin.readlines()
N, M = map(int, lines[0].split())
gift = [[i, 0] for i in range(N)]
for i in range(1, M+1):
n, X = map(int, lines[i].split())
gift[n][1] += X
gift.sort(key=lambda x:(-x[1], x[0]))
for n, X in gift:
print(n, X)