CSP 202012-2 期末预测之最佳阈值

这题也不知道咋回事,我想了个异想天开的做法,也不知道行不行,交上去竟然过了!哈哈哈哈哈哈。
暴力的N^2做法可以得70,我写个异想天开的排序+前缀和做法100。
感觉有必要写个题解,在这里写一下。

本题的大致意思是,给出一堆人的学习努力程度(用一个非负整数表示)和其是否挂科(并不必然成正相关,其中可能混杂学习努力程度高的人也挂科的情况)。要求找到一个学习努力程度基准分数,使得用该基准评判学生的努力程度时,判断对的最多。

我主要利用差分的思想进行解题。对于一个分数,我们其实只需要知道通过与挂科的人数的差值即可。基准分数是否应该低于或高于某一特定学习努力程度分数,在于其能否为总人数作出贡献。例如,如果一个分数有3人通过,3人挂科,则不管选择比他低的基准还是比他高的基准,则都对总的人数做出了3的贡献,可以相互抵消。但若4人通过,3人挂科,则更应该优先选择比其低的基准,因为这样的话,判断对的就多了一个。

首先建立一个map对输入的数据进行排序。由于选择指标的时候只看努力程度不看人,因此可以将同努力程度的人们聚合起来。如果该人挂科,在是否通过的数组cnt里-1,如果通过则+1.这样就产生了一个差分的数组cnt。此时,该数组cnt表示的是在选定该分数作为基准后,通过的人比挂科的人多多少。

然后,对其进行前缀和操作。借助前缀和,我们可以得到数组presum,可以计算选择任意基准分数时,通过的人比挂科的人多多少。还可计算选择任意基准分数时,挂科的人比通过的人多多少(通过对计算值取负)。这样,我们分别计算高于基准分数通过的人比挂科的人多多少,和低于基准分数时挂科的人比通过的人多多少。将他们相加,就可以得到一个判断正确的人数的差分。统计这些差分的最大值,就可以算出对应的基准分数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>

using namespace std;

int m;
map<int, int> stat;
int arrSize = 0;
int y[100005], cnt[100005], presum[100005];

int main() {
    ios::sync_with_stdio(false);
    cin >> m;
    while (m--) {
        int y, result;
        cin >> y >> result;
        stat[y] += result ? 1 : -1;
    }
    for (auto iter = stat.begin(); iter != stat.end(); iter++) {
        int ind = iter->first, v = iter->second;
        y[arrSize] = ind;
        cnt[arrSize] = v;
        arrSize++;
    }
    presum[0]=cnt[0];
    for(int i=1;i<arrSize;i++){
        presum[i]=presum[i-1]+cnt[i];
    }
    int index=0, cmpValue=presum[arrSize-1];
    for(int i=1;i<arrSize;i++){
        int tmpV=presum[arrSize-1]-presum[i-1]*2;
        if(tmpV>=cmpValue){
            cmpValue=tmpV;
            index=i;
        }
    }
    cout<<y[index];
}

CSP 202012-2 期末预测之最佳阈值》有1个想法

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注