CCF认证 2020-12 期末预测之最 佳阈值（100分）

发现最近几次的考试中，第二题基本上都用到了前缀和的思想，本题也是需要用到前缀和思想才能拿到满分，如果用暴力的话，就只能拿到70分。

#include 
#include 
#include 
using namespace std;

const int N = 1e5+1;

int m;

int res;

int y, result;

int Max = 0;

pair pr[N];

int sum[N] = {0};

set st;


int main() {
	scanf("%d",&m);
	
	for(int i = 1; i <= m; ++i) {
		
		scanf("%d%d",&y,&result);
		
		pr[i] = make_pair(y,result);
	}
	
	sort(pr,pr+m+1); //排序
	
	//求挂科情况的前缀和 
	for(int i = 1; i <= m; ++i) sum[i] = sum[i-1] + pr[i].second; 
	
	for(int i = 1; i <=m; ++i) {
		int a = pr[i].first; //选取阈值
		
		if(st.count(a)) continue; //利用set进行去重
		st.insert(a);
		
		int count1 = sum[m] - sum[i-1];
		int count0 = i-1 - sum[i-1];
		int count = count1 + count0; //总共的预测正确的数
		
		if(count >= Max) {
			Max = count;
			
			res = a;
		} 
		
	}
	
	printf("%d",res);
	
	return 0;
}

大家多学习一些C++的STL大有好处，代码会非常简洁明了。