期末预测之最佳阈值

传送门

题意:在当前θ下，统计<θ时,不及格的人数和≥θ时及格的人数。

1.分别使用数组a、b存及格和不及格的同学的y值，使用v存储θ作为指标值。

for(int i=1;i<=n;i++)
{
    int x,y;cin>>x>>y;
    if(y==0) a[cnt1++]=x;//不及格的人
    else b[cnt2++]=x;//及格的人 
    v.push_back(x);//θ:指标 
}

2.将指标v和数组a、b进行排序去重。

sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());//确保每个指标只有一次 
sort(a,a+cnt1);
sort(b,b+cnt2);

3.遍历指标，统计每次<θ时,不及格的人数和≥θ时及格的人数。

for(int i=0;i<(int)v.size();i++)//指标θ 
{
    //cnt2:所有及格了的人数 
    //k1:<θ&&不及格的人数,有k1-1+1个(从0开始) 
    int k1=lower_bound(a,a+cnt1,v[i])-a;
    //k2:<θ&&及格了的人数,cnt2-k2为>=θ且及格了的人数 
    int k2=lower_bound(b,b+cnt2,v[i])-b;
    if(k1+cnt2-k2>=mx)
    {
        mx=k1+cnt2-k2;
        ans=v[i];
    }
}

全部代码

#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+10;
int a[N],b[N];
vector<int>v;
int main()
{
	int n;cin>>n;
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++)
	{
		int x,y;cin>>x>>y;
		if(y==0) a[cnt1++]=x;//不及格的人
		else b[cnt2++]=x;//及格的人 
		v.push_back(x);//θ:指标 
	}
	int mx=-1,ans;
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());//确保每个指标只有一次 
	sort(a,a+cnt1);
	sort(b,b+cnt2);
	for(int i=0;i<(int)v.size();i++)//指标θ 
	{
		//cnt2:所有及格了的人数 
		//k1:<θ&&不及格的人数,有k1-1+1个(从0开始) 
		int k1=lower_bound(a,a+cnt1,v[i])-a;
		//k2:<θ&&及格了的人数,cnt2-k2为>=θ且及格了的人数 
		int k2=lower_bound(b,b+cnt2,v[i])-b;
		if(k1+cnt2-k2>=mx)
		{
			mx=k1+cnt2-k2;
			ans=v[i];
		}
	}
	cout<<ans<<endl;
}