CCF: 202012-2 期末预测之最佳阈值--C++

#include<iostream>
#include<bits/stdc++.h>

using namespace std;



int main()
{
    int n;//m位同学的数据
	int y[100001];//记录m位同学的安全指数
	int result[100001];//记录m位同学最后的挂科情况
	
	cin>>n;
	
	 for(int i=1;i<=n;i++)
	 {
	 	cin>>y[i]>>result[i];
	 }
	 
	 

    
    int p=0; 
    int most=0;//记录最高预测率 
    int res;//记录最终的阈值 
    
    for(int i=1;i<=n;i++)//对每一个可能的阈值分析 
    {
    	p=0;
    	for(int j=1;j<=n;j++)
		{
			if(y[j]<y[i]&&result[j]==0)//安全指数小于阈值 就挂科 
			p++;
			
			if(y[j]>=y[i]&&result[j]==1)//安全指数大于阈值 不挂科
			p++; 
		 } 
		 
		 if(p>most) //准确率更高 
		 { 
		 most=p;
		 res=y[i]; 
		 }
		 
		 if(p==most&&y[i]>res)//准确率相同就用更大的作为阈值
		{
		 most=p;
		 res=y[i];
		 } 
		 
	}
	
	cout<<res;


	
    
    return 0;
}

暴力求解：只有七十分

优化：思路差不多：根据安全指数从小到大排序之后，记录第i个安全指数前面的0出现个数以及1出现个数，那么第i个安全指数的预测成功个数就等于前面0的个数d[i]加上后面1的个数，后面1的个数等于d[n]-d[i-1];注意是减去d[i-1]，否则会漏了result[i]==1的情况

但是还是有些小细节思考不周全，还是会超时~~

可能是排序花费时间太多了？

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

     int sum[100001];//重复次数 
	 int same1[100001];//代表某个安全指数对应结果为1的个数 
     int y[100001];//记录m位同学的安全指数
	 int result[100001];//记录m位同学最后的挂科情况
	
	int d[100001];//d[i]表示阈值为i时i前面的 预测成功的个数（i前面result==0的个数） 
	int d1[100001];//i前面为1的个数 
	
int main()
{
    int n;//m位同学的数据
	
	memset(d,0,sizeof d); 
	
	result[0]=-1;
	
	cin>>n;
	
	 for(int i=1;i<=n;i++)
	 {
	 	cin>>y[i]>>result[i];
	 }
	 
	 
	 
	 int tempi;//记录当前位置的安全指数
	 int tempr;//记录当前位置的挂科结果 
	 int min=1000;//记录最小值 
	 int flagi;//记录选择出来的最小值的位置 
	
	 
	 for(int i=1;i<=n;i++)//进行选择排序 
	 {
	 	tempi=y[i];
	 	tempr=result[i];
	 	min=100000001;
	 	for(int j=i+1;j<=n;j++)
	 	{
	 		if(y[j]<min)
			 {
			 min=y[j];
			 flagi=j;//记录目前最小值所在点 
			  } 
		 }
		 
		 if(min<tempi) 
		 {
		 	y[i]=min;//最小的往前放 
		 	result[i]=result[flagi];
		 	
		 	//前面的往原本最小的地方放
			 y[flagi]=tempi;
			 result[flagi]=tempr; 
		 }
		 
		 if(result[i]==0)
		 {
		 	d[i]=d[i-1]+1;
		 	d1[i]=d1[i-1]; 
		  } 
		    else
			{
				d[i]=d[i-1];
				d1[i]=d1[i-1]+1;
			 } 
	 }
	 
	 
	 
	 y[0]=-1;
	 
	 for(int i=1;i<=n;i++)
	 {
	 	if(y[i]==y[i-1])
		 {
		 	int s=i;
		 	same1[i-1]+=result[i-1];
		 	sum[i-1]++;
		 	while(y[s]==y[s-1])
			 {
			 same1[i-1]+=result[s];//重复的那个安全指数有几个结果为1
			 sum[i-1]++;//有几个重复
			 s++;
			  }
			  
			  s--;
			  while(s>=i-1)
			  {
			  	d[s]=d[i-2]+sum[i-1]-same1[i-1];
			  	d1[s]=d1[i-2]+same1[i-1];
			  	s--;
			   } 
			   
			   i+=sum[i-1]-1; 
		 	 
		 }
	 }
	 
    
    int p=0; //当前阈值下的预测率 
    int most=0;//记录最高预测率 
    int res;//记录最终的阈值 
    
    for(int i=1;i<=n;i++)//对每一个可能的阈值分析 
    {
    	if(sum[i]!=0)//有重复 
    	{
    	p=d[i-1]+same1[i]+(n-(i+sum[i]-1))-(d[n]-d[i])  ;	//前面0的个数加上重复的数字1的个数+后面1的个数 
		i+=sum[i]-1;
		}
		else
		{
		
//    	if(result[i]==0)
//    	{//d[i]多了一个本身的0，但是本身的0不能加入预测正确的p中 
//    		p=d[i]+((n-i)-(d[n]-d[i]))-1;//i前面预测正确的个数+后面(i+1到n-1)预测正确（1）的个数
//		}
//		else//本身是1，预测正确的个数加1 
//			p=d[i]+((n-i)-(d[n]-d[i]))+1;//i前面预测正确的个数+后面(i+1到n-1)预测正确（1）的个数

         p=d[i-1]+d1[n]-d1[i-1];
    	 }

		
		if(p>=most) 
		{
			most=p;
			res=y[i];
			
		 } 
    }

cout<<res;
	
    
    return 0;
}

CCF 202012-1 期末预测之最佳阈值 C++解决思路附代码_期末预测之最佳阈值c++的不同解法及效率-CSDN博客