【題解】ZeroJudge e826: 1. 粉絲見面會 (Fans)

【題目敘述】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)
分享本文 Share with friends