题目

 

 

过程

思路

第一次没用前缀和，暴力求解得50分。

采用前缀和方法。

1. 对原数组stu[i]进行排序。

2. 计算前缀和数组s[]，s[i]表示安全指数的y_i的前缀和，即安全指数小于等于y_i时的实际挂科情况，y_i之前有多少个未挂科（result_i=1）。

3. 按照预测，以y_i为阈值，小于y_i的应该全部为0，大于等于y_i的应该全部为1。将预测与实际情况进行对比，计算预测正确的次数num。

• num0=i-1-s[i-1]。小于y_i有i-1个结果，减去未挂科情况s[i-1]，即为预测正确的挂科情况。
• num1=s[m]-s[i-1]。大于等于y_i有m-(i-1)个结果，s[m]和s[i-1]前缀和相减，即为预测正确的未挂科情况。
• num=num0+num1。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
	int y;
	int result;
}stu[100005];
int s[100005];
bool cmp(struct node a,struct node b){
	return a.y<b.y;
}
int main()
{
	int m;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>stu[i].y>>stu[i].result;
	}
	sort(stu+1,stu+1+m,cmp);
	//计算前缀和
	for(int i=1;i<=m;i++){
		s[i]=s[i-1]+stu[i].result;
	}
	int max=0,res=0,pre=0;
	for(int i=1;i<=m;i++)
	{
		if(stu[i].y==pre) continue;
		pre=stu[i].y;
		//cout<<pre<<endl;
		int num1=s[m]-s[i-1];
		int num0=i-1-s[i-1];
		int num=num0+num1;
		//cout<<num<<endl; 
		if(num>=max)
		{
			max=num;
			res=stu[i].y;
		}
	}
	cout<<res;
	return 0;
 } 

结果