ccf真题及答案，CCF202012-2 期末预测之最优阈值

数据也就200个，不算大。 于是先试一下暴力枚举，得了70分......

显然题目数据没那么简单，应该有很大的优化部分，比如对阈值进行排序或是选用更优秀的数据结构和算法，都是可以的。

也可以排序后分别统计每个位置对应的小于该值0的个数 以及 大于该值1的个数

ccf真题及答案，试题编号： 202012-2
试题名称： 期末预测之最佳阈值
时间限制： 1.0s
内存限制： 512.0MB
问题描述：

样例1输入

6
0 0
1 0
1 1
3 1
5 1
7 1

样例1输出

3

ccf2021答案。
样例1解释
按照规则一，最佳阈值的选取范围为0,1,3,5,7。
θ=0时，预测正确次数为4；
θ=1时，预测正确次数为5；
θ=3时，预测正确次数为5；
θ=5时，预测正确次数为4；
θ=7时，预测正确次数为3。
阈值选取为1或3时，预测准确率最高；
所以按照规则二，最佳阈值的选取范围缩小为1,3。
依规则三，θ*=max1,3=3。

样例2输入

8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0

样例2输出

100000000

子任务
70%的测试数据保证m<=200；
全部的测试数据保证1<=m<=105。

70分的暴力枚举解题代码：

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
using namespace std;
int m,y,r;
int ansy=-1,maxsum=-1; //保存最后阈值结果和最大正确预测数量
struct node{int y,r;
}nd[201];
int main(){scanf("%d",&m);int cnt = 0;while(1){scanf("%d%d",&nd[cnt].y,&nd[cnt].r);cnt++;	if(cnt == m) break;}for(int i=0;i<m;i++){int nowy = nd[i].y,sum=0;for(int j=0;j<m;j++){if((nd[j].y >= nowy && nd[j].r == 1) || (nd[j].y < nowy && nd[j].r == 0) )sum++;}//每次遍历完一个阈值之后更新结果if(sum > maxsum) {ansy = nowy; maxsum = sum;}else if(sum == maxsum) ansy = max(nowy,ansy);}printf("%d",ansy);return 0;
}

100分的前后缀和解题代码：

/* CSP202012-2 期末预测之最佳阈值 */#include <iostream>
#include <algorithm>
#include <cstdio>using namespace std;const int M = 100000;
pair<int, int> a[M + 1];
int prefix[M + 2], suffix[M + 2], p[M + 2];int main()
{int m, i;scanf("%d", &m);for(i = 1; i <= m; i++)scanf("%d%d", &a[i].first, &a[i].second);sort(a + 1, a + 1 + m);// 前缀和prefix[0] = 0;for(i = 1; i <= m; i++)prefix[i] = prefix[i - 1] + (a[i].second == 0 ? 1 : 0);// 后缀和suffix[m + 1] = 0;for(i = m; i >= 1; i--)suffix[i] = suffix[i + 1] + (a[i].second == 1 ? 1 : 0);int pos = 1;p[1] = 1;for(i = 1; i <= m; i++)if(a[i].first == a[i - 1].first)p[i] = pos;elsep[i] = (pos = i);int ans = 0, mx = 0;for(i = 1; i <= m; i++) {int cur = prefix[p[i] - 1] + suffix[i];if(cur >= mx)mx = cur, ans = a[i].first;}printf("%d\n", ans);return 0;
}