CCF202012-2期末预测之安全指数

题目背景
考虑到安全指数是一个较大范围内的整数、小菜很可能搞不清楚自己是否真的安全，顿顿决定设置一个阈值 ，以便将安全指数 转化为一个具体的预测结果——“会挂科”或“不会挂科”。

因为安全指数越高表明小菜同学挂科的可能性越低，所以当 时，顿顿会预测小菜这学期很安全、不会挂科；反之若 ，顿顿就会劝诫小菜：“你期末要挂科了，勿谓言之不预也。”

那么这个阈值该如何设定呢？顿顿准备从过往中寻找答案。

题目描述
体来说，顿顿评估了 位同学上学期的安全指数，其中第 （）位同学的安全指数为
，是一个
范围内的整数；同时，该同学上学期的挂科情况记作
，其中 表示挂科、 表示未挂科。

相应地，顿顿用 表示根据阈值 将安全指数 转化为的具体预测结果。
如果
与
相同，则说明阈值为 时顿顿对第 位同学是否挂科预测正确；不同则说明预测错误。

#include<bits/stdc++.h>
using namespace std;
struct YR 
{int y;//输入的y int result;//输入的result 
};
YR A[int(1e5+5)];
bool cmp(YR a,YR b)
{return a.y<=b.y;
}
void Diplay(YR &a)
{cout<<a.y<<" "<<a.result<<endl;
}
/*
分析题目，数据分数在1e5，暴力法时间会超出。寻找相邻y之间的数量关系。
最直接的就是依据y对数据排序，寻找当前y的预测正确次数与前一项y的关系。
int maxThta=-1,maxcount=0;记录最大阈值maxThta以及预测正确次数maxcount
int R0=0,R1=0;//记录小于当前y（此时y作为阈值）时result==0的个数，大于等于y时result==1个数 
预测正确次数计算方法：=R0+R1 int tem0=0,tem1=0;//等于当前A[i].y数字时result==0个数和result==1个数 
则：
下一个y的预测正确次数=（R0+tem0） +（R1-tem1）依次规律依次计算出所有y作为阈值时的正确次数，并在计算过程中记录最大maxcount  
*/
int main()
{int n;cin>>n;int temy,temr;for(int i=0;i<n;++i){scanf("%d%d",&temy,&temr);A[i].y=temy;A[i].result=temr;}sort(A,A+n,cmp);//依据y排序 
//	for(int i=0;i<n;++i)
//	{
//		Diplay(A[i]);
//	}int maxThta=-1,maxcount=0;int R0=0,R1=0;//统计识别0的正确个数，1的正确个数 int tem0=0,tem1=0;//当前A[i].y数字的0个数和1个数 int k;for(int i=0;i<n;++i)//求第一个数的 R0，R1，tem1，tem0，并记录第一y的最后下标k {if(A[i].result==1){++R1;} if(A[i].y==A[0].y){if(A[i].result==1)tem1++;else tem0++;k=i;}}maxcount=R0+R1;//初始化 maxThta=A[0].y;//	cout<<A[0].y<<" "<<maxcount<<tem1<<" "<<tem0<<endl; for(int i=k+1;i<n;++i)//从第二个y开始计算 {R0=R0+tem0;R1=R1-tem1;//当前y作为阈值预测准确数 R0+R1 
//		cout<<A[i].y<<" "<<R0+R1;if(maxcount<=R0+R1)//记录最大的预测准确数以及maxThta {maxcount=R0+R1;if(A[i].y>maxThta)maxThta=A[i].y;}int j=i;tem0=tem1=0;for( ;i<n;++i)//统计当前y的result==0个tem0，以及result==1个数tem1 {if(A[j].y==A[i].y){if(A[i].result==1)++tem1;else ++tem0;}else break;}--i;
//		cout<<tem1<<" "<<tem0<<endl;}cout<<maxThta<<endl;return 0;
}