首页 计算机科学 csp

# 题目

1661851584070

6
0 0
1 0
1 1
3 1
5 1
7 1
8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0
# 理解
题目要求的求最高准确率即为求预测正确的同学的人数，按照安全指数和挂科情况进行排序后，在取定某同学的安全指数作为阈值的情况下，即求数组左侧的 result 值为 0 的同学人数和右侧的 result 值为 1 的人数之和。容易想到用前缀和来解决。
要注意的是，由于正确率公式中存在一个大于等于，所以在排序时，对于具有相同安全指数但 result 值不同的同学，让 result 值为 1 的放在数组前面。
# 解答
#include <iostream>
#include <stdio.h>
#include <map>
#include <algorithm>
//#define aaa
#define ll long long
using namespace std;
map<ll, ll> mp;
int m;
// 选择阈值之后，需要计算正确率
/*
* 如果按照安全指数进行排序，
* 
* 对于不同的同学，相同的安全指数可以有不同的结果
* 
* 右边 1 的个数
* 
* 左边 0 的个数
* 
* 必然要遍历所有可能取得的阈值，所以目标是优化求解准确率的过程
* 
* 两个前缀和数组 sum1 和 sum2 分别表示 0 的个数和 1 的个数
* 
* 在遍历阈值的时候，判断当前取得的阈值是否和上一次取得的阈值相同，如果相同，则跳过
* 
* 当安全指数相同而结果不同时，结果为 1 的排在前面。假如为 0 的排在前面
* 
* 0 0 1 1
* 
* 1 1 0 0
* 
* 右边的 1 的个数计算正确，左边 0 的个数计算正确
*/
const int maxm = 100005;
struct mate
{
    ll y;
    ll result;
}mates[maxm];
bool cmp(mate m1, mate m2) {
    if (m1.y == m2.y)
        return m1.result > m2.result;
    else
        return m1.y < m2.y;
}
ll sum1[maxm]; //0 的个数
ll sum2[maxm];  //1 的个数
int main()
{
#ifdef aaa
    freopen("stdin.txt", "r", stdin);
#endif // aaa
    cin >> m;  //m 为人数
    for (int i = 1; i <= m; i++) {
        ll y, result;
        cin >> y >> result;
        mates[i].y = y;
        mates[i].result = result;
    }
    sort(&mates[1], &mates[m + 1], cmp);
#ifdef aaa
    for (int i = 1; i <= m; i++) {
        cout << mates[i].y << " " << mates[i].result << endl;
    }
    cout << "---------" << endl;
#endif // aaa
    // 求出前缀和数组
    for (int i = 1; i <= m; i++) {
        if (mates[i].result) {
            sum1[i] = sum1[i - 1];
            sum2[i] = sum2[i - 1] + 1;
        }
        else {
            sum1[i] = sum1[i - 1] + 1;
            sum2[i] = sum2[i - 1];
        }
    }
    // 遍历取阈值
    ll pre;  // 保存前一步的阈值
    ll theta;
    ll Maxcor; // 最大正确率
    for (int i = 1; i <= m; i++) {
        if (i == 1) {
            Maxcor = sum2[m] - sum2[i - 1] + sum1[i - 1];
            theta = mates[i].y;
            pre = theta;
            continue;
        }
        if (mates[i].y == pre)
            continue;
        pre = mates[i].y;
        
        ll curCor = sum2[m] - sum2[i - 1] + sum1[i - 1];
        if (Maxcor <= curCor) {
            theta = mates[i].y;
            Maxcor = curCor;
        }
    }
    cout << theta;
    return 0;
}