CSP 2020年12月试题

第二题 期末预测之最佳阈值

思路

这次考试是刚转完专业考的，迷迷糊糊的只准备了前两道。但是好像和以前的题不一样，这一次难度加大了，暴力搞只能过70%测试点，导致当时200分的目标都没实现。。
这次再看这道题，有了一些思路，如果按照安全指数进行降序排序的话，某一点的预测精准度等于前面结果为0的个数+该点及之后同数值的点为1的个数+之后为0的个数，为了提高效率可做两步处理

  1. 输入时统计结果为0的个数
  2. 遍历时记录前面为1的个数
    这样根据前两个数据就可以算出预测正确的个数
    然后从头到尾扫描寻找预测效果最好的那个（注意同一预测效果不同阈值的处理）

程序

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int y;
    int r;
    int prenum;
    int p;
} s[100002];
bool cmp(node a, node b)
{
    return a.y > b.y;
}
int main()
{
    int n, sum0 = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i].y >> s[i].r;
        if (s[i].r == 0)
        {
            sum0++;
        }
    }
    sort(s, s + n, cmp);
    int pre1 = 0;
    for (int i = 0; i < n; i++)
    {
        s[i].prenum = pre1;
        int j, t = 0;
        s[i].p = pre1;
        for (j = i; j < n && s[j].y == s[i].y; j++)
        {

            s[i].p += s[j].r;
        }
        //cout << s[i].y << ' ' << s[i].r << ' ' << s[i].p << ' ' << sum0 - (j - s[i].p) << endl;
        s[i].p += sum0 - (j - s[i].p);
        pre1 += s[i].r;
    }
    int max = -1, result;
    for (int i = 0; i < n; i++)
    {
        //cout << s[i].y << ' ' << s[i].p << endl;
        if (max < s[i].p)
        {
            max = s[i].p;
            result = s[i].y;
        }
    }
    cout << result;
}