ccf-csp-2020-12-2期末预测之最佳阈值（c++满分题解）

这个题暴力是可以有70分的，下面是暴力代码：（注释写的比较清楚了，也很好理解）

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
bool sort1(pair<int,int> vec1,pair<int,int> vec2)//对阈值从小到大排序
{
	return vec1.first<=vec2.first;
}
int main()
{
	int n;
	cin>>n;
	vector<pair<int,int>> vec;
	set<int> set1;
	for(int i=0;i<n;++i)
	{
		int a,b;
		cin>>a>>b;
		vec.push_back(make_pair(a,b));
		set1.insert(a);//set去重记录有哪些阈值
	}
	sort(vec.begin(),vec.end(),sort1);
	int ans=0;//记录最大预测正确次数
	int res=0;//记录最大预测正确次数的阈值
	for(auto it=set1.begin();it!=set1.end();it++)//从所有的阈值开始遍历
	{
		int num=0;
		int temp=*it;
		for(int i=0;i<n;++i)//遍历所有情况，得出每个阈值的正确次数
		{
			if((vec[i].first<temp && vec[i].second==0) || (vec[i].first>=temp && vec[i].second==1))
				num++;
		}
		if(num>=ans)
		{
			ans=max(ans,num);//得到最大值
			res=temp;
		} 

	}
	cout<<res<<endl;
		
} 

接下来是100分题解，

我先说一下我自己的思路，我是看到这个样例1的详细解释我才想到这个

去重记录所有阈值，0 1 3 5 7

然后对0计算正确次数，会发现是11，31，51，71 这四个样本，

如果我们对1计算正确次数，发现是0 0，11，31，51，71这五个样本，很容易发现有重复的样本，如果暴力计算，这些就是超时的根源，并且他们是有规律的，1与0相比多的0 0，为了使规律更加明显，我们看一下对下面几个样本计算正确次数

3： 0 0， 1 0 ，3 1 ，51， 71

5：0 0，1 0，5 1，7 1

现在规律 就很明显了，加入说0的正确次数是num,那么对1求正确次数的时候只需要看0的样本，有0 0样本的话，num++(因为对1来说是正确的样本),有0 1样本的话，num--（对1来说是不正确的样本）；如果对2求正确次数，同理，只要看1 0（num++)的个数与11(num--)的个数。。。。对所有阈值进行计算，得出正确次数，这样的话遍历的次数就少了很多，相当于总共遍历了两次所有样本（一次是求0的num值，第二次是求剩下的所有num值）

下面是代码：

#include<iostream>
#include<set>
#include<vector>
#include<algorithm> 
using namespace std;
bool sort1(pair<int,int> vec1,pair<int,int> vec2)
{
	return vec1.first<=vec2.first;
}
int main()
{
	int n;
	cin>>n;
	vector<pair<int,int>> vec;
	set<int> set1;
	for(int i=0;i<n;++i)
	{
		int a,b;
		cin>>a>>b;
		vec.push_back(make_pair(a,b));
		set1.insert(a);
	}
	sort(vec.begin(),vec.end(),sort1);//记得排序
	auto it=set1.begin();
	int temp=*it;
	int sum=0;
	for(int i=0;i<n;++i)//对第一个元素求num值
	{
		if((vec[i].first<temp && vec[i].second==0) || (vec[i].first>=temp && vec[i].second==1))
			sum++;
	}
	int ans=sum;
	int res=temp;//res是最后的结果
	it++;
	int index=0;
	for(;it!=set1.end();it++)//对剩下的阈值开始计算正确次数num
	{
		for(int i=index;i<n;++i)
		{
			if(vec[i].first!=temp)//0 1 3 5 7//
				break;
			if(vec[i].first==temp && vec[i].second==1)//对于1来说只需要计算0 0， 01 的个数，对于3来说只需要计算1 0， 1 1的个数
				sum--;
			else if(vec[i].first==temp && vec[i].second==0)
				sum++;
			index++;
		}
		if(sum>=ans)
		{
			ans=max(sum,ans);//求最值
			res=*it; 
		}
		temp=*it;
	}
	cout<<res<<endl;
}

下面是提交记录截图：

写的有点着急，如有错误，感谢指出，希望和大家一起共同进步