#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];//重復的那個安全指數有幾個結果為1sum[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博客