淘先锋技术网

首页 1 2 3 4 5 6 7

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

嗨！多一嘴：最近开始准备CSP认证，所以就简单的做个刷题记录，督促自己不断努力！解决方式是按照我这个菜鸟的理解去解决的，所以代码虽然正确，但可能不是最佳的解决算法，若一起学习的小伙伴有更好的解决思路，可以一起分享学习，一起进步呀！

1、问题描述

在这里插入图片描述

2、输入输出格式

在这里插入图片描述

样例1输入
6
0 0
1 0
1 1
3 1
5 1
7 1
样例1输出
样例1解释

在这里插入图片描述

样例2输入
8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0
样例2输出
子任务

在这里插入图片描述

3、代码

#include<iostream>
#include<algorithm>
using namespace std;

struct Student{
    int y;
    int result;
};

bool cmp(Student s1,Student s2)
{
    return s1.y < s2.y;
}

int main()
{
    Student student[100005];
    int count_0[100005]={0};
    int count_1[100005]={0};
    //输入数据，存到结构体数组中
    int m;
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin>>student[i].y>>student[i].result;
    }
    //排序，由y值从小到大
    sort(student,student+m,cmp);
    //统计小于每个student[i].y的0的个数，也就是预测结果和实际结果都为0的个数
    int i = 0 , j = 1;
    int coing_0 = 0 , coing_1 = 0;
    while(j<m)
    {
        if(student[j].y==student[i].y)
        {
            //避免漏掉相同y值的计数情况
            j++;
            continue;
        }
        //从i到j统计累计的0的个数，并加上之前已有的0的个数（temp）
        int temp = 0;
        while(i<j)
        {
            if(student[i].result==0) temp++;
            count_0[i] = coing_0;
            i++;
        }
        coing_0 += temp;
    }
    //统计最后几个，避免j达到m之后而漏掉了最后几个数据
    while(i<j)
    {
        count_0[i] = coing_0;
        i++;
    }
    //统计大于等于每个student[i].y的1的个数，也就是预测结果和实际结果都为1的个数
    for(int i=m-1;i>=0;i--)
    {
        if(student[i].result==1) coing_1++;
        count_1[i] = coing_1;
    }
    //输出最大阈值
    int ans = student[0].y;
    int num = count_0[0] + count_1[0];
    for(int i=1;i<m;i++)
    {
        if(count_0[i] + count_1[i] >= num)
        {
            num = count_0[i] + count_1[i];
            ans = student[i].y;
        }
    }
    cout<<ans<<endl;
    return 0;
}