高中生程式解題:e826: 1. 粉絲見面會 (Fans)－資工趴趴熊的小天地

Content

Y19m10_a1 粉絲見面會 (Fans) 2019年10月TOI練習賽潛力組 {題目連結}

問題敘述

浩哥是知名的實況主，他在實況的時候，常常有許多粉絲送他虛擬禮物。有一天，浩哥想要舉辦一場粉絲見面會，而入場順序則由粉絲排行榜的排名來決定。請你幫浩哥製作一個粉絲排行榜，依粉絲的贈禮總金額由大到小列出結果。

評分說明此題目測資分成三組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數。各組詳細限制如下。

第一組 (10 分) : 1<=N<=10、0<=M<=30
第二組 (30 分) : 1<=N <=10^3、0<=M<=10^4
第三組 (60 分) : 1<=N<=10^5、0<=M<=10^6

Input

第一列有兩個正整數 N、M（1<=N<=10^5、0 <=M<=10^6），代表有 N 個粉絲，粉絲的編號為 0～(N－1)，以及 M 個贈禮紀錄。接著 M 列為贈禮紀錄，每列有兩個正整數，為當筆紀錄的粉絲編號和贈禮金額 X（1<=X<=100）。

Output

請輸出 N 列，以贈禮總金額由大到小排序粉絲資料，每列皆有兩個整數，以一個空白隔開，分別為粉絲編號以及贈禮總金額。贈禮總金額相同時，先輸出粉絲編號較小者。

Sample Input #1

Sample Output #1

1 14
0 13
2 7

Sample Input #2

3 1
1 10

Sample Output #2

1 10
0 0
2 0

C++

#include <iostream>
#include <algorithm>
using namespace std;

struct node{
	int number;
	int value;
};

bool cmp(node &a, node &b){
	if(a.value!=b.value)return a.value>b.value;
	else return a.number<b.number;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m; //n個粉絲 m筆紀錄 
	int N,M; //裡面的每一筆紀錄 
	while(cin>>n>>m){
		node fans[n];
		
		for(int i=0;i<n;i++){
			fans[i].number=i;
			fans[i].value=0;
		}
		
		for(int i=0;i<m;i++){
			cin>>N>>M;
			fans[N].value+=M;
		}
		
		sort(fans,fans+n,cmp);
		
		for(int i=0;i<n;i++){
			cout<<fans[i].number<<" "<<fans[i].value<<"\n";
		}
	}
	return 0;
}

python解法一

from sys import stdin
for A in stdin:
    n,m=map(int,A.split())
    gift=[[i,0]for i in range(n)]
    for _ in range(m):
        a,b=map(int,stdin.readline().split())
        gift[a][1] +=b
    gift.sort(key=lambda x:(-x[1],x[0]))
    for a,b in gift:
        print(a,b)

python解法二

from sys import stdin
A=stdin.readlines()
n,m=map(int,A[0].split())
gift=[[i,0]for i in range(n)]
for i in range(1,m+1):
    a,b=map(int,A[i].split())
    gift[a][1] +=b
gift.sort(key=lambda x:(-x[1],x[0]))
for a,b in gift:
    print(a,b)