題目

?

?

過程

思路

第一次沒用前綴和，暴力求解得50分。

采用前綴和方法。

1. 對原數組stu[i]進行排序。

2. 計算前綴和數組s[]，s[i]表示安全指數的y_i的前綴和，即安全指數小于等于y_i時的實際掛科情況，y_i之前有多少個未掛科（result_i=1）。

3. 按照預測，以y_i為閾值，小于y_i的應該全部為0，大于等于y_i的應該全部為1。將預測與實際情況進行對比，計算預測正確的次數num。

• num0=i-1-s[i-1]。小于y_i有i-1個結果，減去未掛科情況s[i-1]，即為預測正確的掛科情況。
• num1=s[m]-s[i-1]。大于等于y_i有m-(i-1)個結果，s[m]和s[i-1]前綴和相減，即為預測正確的未掛科情況。
• num=num0+num1。

代碼

#include<bits/stdc++.h>
using namespace std;
struct node{int y;int result;
}stu[100005];
int s[100005];
bool cmp(struct node a,struct node b){return a.y<b.y;
}
int main()
{int m;cin>>m;for(int i=1;i<=m;i++){cin>>stu[i].y>>stu[i].result;}sort(stu+1,stu+1+m,cmp);//計算前綴和for(int i=1;i<=m;i++){s[i]=s[i-1]+stu[i].result;}int max=0,res=0,pre=0;for(int i=1;i<=m;i++){if(stu[i].y==pre) continue;pre=stu[i].y;//cout<<pre<<endl;int num1=s[m]-s[i-1];int num0=i-1-s[i-1];int num=num0+num1;//cout<<num<<endl; if(num>=max){max=num;res=stu[i].y;}}cout<<res;return 0;} 

結果