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

http://118.190.20.162/view.page?gpid=T122

4.06 21：15-21：52 第一次提交-运行错误，得分70，估计是大于200的测试未通过。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int MAXN = 1000;
map<int, int> acc;
int y[MAXN];
int result[MAXN]; 
vector<int> ans;
int ansn = 0;

int predict(int y, int sita){
    if(y < sita){
        return 0;
    }else{
        return 1;
    }
}

bool cmp(int a, int b){
    return a > b;
}

int main(){
    int m;
    scanf("%d", &m);
    long long sum = 0;
    for(int i = 0; i < m; i++){
        scanf("%d %d", &y[i], &result[i]);
        //cin >> y[i] >> result[i];
        acc[y[i]] = 0;
    }
    map<int, int> :: iterator it;
    int maxacc = 0;
    for(it = acc.begin(); it != acc.end(); it++){
        for(int i = 0; i < m; i++){
            if(result[i] == predict(y[i], it->first)){
                it->second += 1;
            }
        }
        //cout << it->first << " " << it->second << endl;
        if(maxacc <= it->second){
            ans.push_back(it->first);
            maxacc = it->second;
            //cout << "max" <<it->first << endl;
        }
    }
    sort(ans.begin(), ans.end(), cmp);
    cout << ans[0] << endl;
    return 0; 
}

第二次提交把MAXN设置到10000，运行超时。
第三次提交不使用vector 直接记录maxy，仍然超时。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int MAXN = 100000;
map<int, int> acc;
int y[MAXN];
int result[MAXN]; 
vector<int> ans;
int ansn = 0;

int predict(int y, int sita){
    if(y < sita){
        return 0;
    }else{
        return 1;
    }
}

bool cmp(int a, int b){
    return a > b;
}

int main(){
    int m;
    scanf("%d", &m);
    long long sum = 0;
    for(int i = 0; i < m; i++){
        scanf("%d %d", &y[i], &result[i]);
        //cin >> y[i] >> result[i];
        acc[y[i]] = 0;
    }
    map<int, int> :: iterator it;
    int maxacc = 0;
    int maxy = 0;
    for(it = acc.begin(); it != acc.end(); it++){
        for(int i = 0; i < m; i++){
            if(result[i] == predict(y[i], it->first)){
                it->second += 1;
            }
        }
        //cout << it->first << " " << it->second << endl;
        if(maxacc <= it->second){
            //ans.push_back(it->first);
            maxacc = it->second;
            if(maxy < it->first) {
                maxy = it->first;
            }
            //cout << "max" <<it->first << endl;
        }
    }
    //sort(ans.begin(), ans.end(), cmp);
    cout << maxy << endl;
    return 0; 
}