题面

【题目描述】

老师在开学第一天就把作业全都布置了，每份作业如果在规定时间内上交的话就能够得到 一定的学分。每份作业的规定时间和学分可能是不同的。现在你的能力是每天能且仅能完成一份作业，你需要找到一种完成作业的顺序使得总学分 最大。

【输入格式】

第一行一个整数 n 表示作业的数量。 接下来 n 行，每行包含两个整数，分别表示一份作业的规定时间和学分。

【输出格式】

输出一行一个整数表示最大的总学分。

【样例输入】

7

1 6

1 7

3 2

3 1

2 4

2 5

6 1

【样例输出】

15

【数据范围】 对于 $20$% 的数据，$n ≤ 10 3$。 对于 $40$% 的数据，$n ≤ 10 4$。 对于 $60$% 的数据，$n ≤ 10 5$。 对于 $100$% 的数据，$n ≤ 10 6$，作业的规定时间不超过 $7×10 5$，保证最终答案不超过$2^63− 1$

提交记录

蒟蒻代码

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline int read(){

	int s=0;

	int w=1;
	
   	char ch=getchar();

	for(long long i=1;ch<'0'||ch>'9';ch=getchar())
	
    	if(ch=='-')
    	
			w=-1;
			
   	for(int i=1;ch>='0'&&ch<='9';ch=getchar())
   	
		s=s*10+ch-'0';
		
	return s*w;

}

int n;

struct node{
	
	int t;
	
	int p;
	
};

bool cmp(node a,node b){
	
	if(a.t<b.t)
	
		return true;
		
	else if(a.t==b.t)
	
		if(a.p<b.p)
		
			return false;
			
		return true;
		
	return false;
	
}

node a[700086];

bool day[700086]; 

ll sum;

int flag;

int main(){

//	freopen("homework.in","r",stdin);
//	
//	freopen("homework.out","w",stdout);
	
	n=read();
	
	for(int i=1;i<=n;i++){
		
		a[i].t=read();
		
		a[i].p=read();
		
	}
	
	sort(a+1,a+1+n,cmp);
	
	for(int i=1;i<=n;i++){
		
		if(!day[a[i].t]){
			
			sum+=a[i].p;
			
			day[a[i].t]=true;
			
		}
		
	}
	
	cout<<sum;

	return 0;
	
}