【CSP CCF记录】202012-2 期末预测之最佳阈值

题目

 

 

过程

思路

第一次没用前缀和，暴力求解得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;
 } 

结果

原文地址：https://blog.csdn.net/m0_73733846/article/details/139067414

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！