索引

历年CSP认证考试真题题解总汇持续更新

2020-12-2 期末预测之最佳阈值 排序+差分+前缀和

这题并不算难，但也不是直接套公式那么简单，也有一些需要注意的问题。但是我的思路还是来回摇摆，写了一半发现好像不太行，但是又想不到别的思路又返回去写，废了很多时间，所以在开始写代码之前一定要确定思路，想好流程，看看样例过不过得了，然后再开始写代码

思路

第二题一般的思路都是往前缀和上靠，一看数据是$10^5$ ，所以复杂度是$O(n^2)$肯定不可行，并且其实我们遍历一次学生数据的数组就可以把所有的阈值对应的正确率算出来。也就是可以找到一个s（学生数据）到$\theta$​（阈值）的一个映射的，一个y（成绩）可以对应一个阈值区间增加1个正确的。

如果 result=0 则y-成绩最高的 区间增加1 （因为比他大的阈值都可以让他result=0）

如果result=1 则成绩最低的-y-1区间增加1 （因为比他小的阈值都可以让他result=1）

但是如果只用这个思路还有问题，就是成绩有重复的话不能直接取y，要把所有和y相同的都加进去

遇到的问题

1. 上面重复成绩的问题

一开始没有意识到成绩重复的问题，意识到了，以为不会影响，但是没有细想，直到最后样例没过，才想到必须要考虑重复的问题。

开始考虑这个问题后，思路逐渐清晰

然后就是下标的问题，因为我是从小到大排序的，所以向后找到第一个成绩不一样的，再进行差分的运算。

        if (s[i].r == 0)
        {
            int j = i;
            while (j <= m && s[i].y == s[j].y) // 向后找到第一个不等于他的
                j++;
            theta[j]++;
            theta[m + 1]--;
        }
        else
        {
            int j = i + 1;
            while (j <= m && s[i].y == s[j].y) // 向后找到第一个不等于他的
                j++;
            theta[j]--;
            theta[1]++;
        }

过了样例，一次就拿到了100分

完整代码

#include <bits/stdc++.h>
using namespace std;
int m;
int theta[100001]; // 存储对应阈值 对应的正确的数量
struct stu
{
    int y;
    int r;
} s[100001];
bool cmp(struct stu a, struct stu b)
{
    return a.y < b.y;
}
int main()
{
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> s[i].y >> s[i].r;
    }
    sort(s + 1, s + m + 1, cmp);
    for (int i = 1; i <= m; i++)
    {
        if (s[i].r == 0)
        {
            int j = i;
            while (j <= m && s[i].y == s[j].y) // 向后找到第一个不等于他的
                j++;
            theta[j]++;
            theta[m + 1]--;
        }
        else
        {
            int j = i + 1;
            while (j <= m && s[i].y == s[j].y) // 向后找到第一个不等于他的
                j++;
            theta[j]--;
            theta[1]++;
        }
    }
    int max = -1;
    for (int i = 1; i <= m; i++)
    {
        theta[i] += theta[i - 1];
        if (max == -1 || theta[i] >= theta[max]) // 如果相同则找到最大的
        {
            max = i;
        }
    }
    cout << s[max].y;
    return 0;
}