文章目录
0 效果
此为暴力求解的算法，没有通过200～105的数据测试。
1 题目
样例1输入
6
0 0
1 0
1 1
3 1
5 1
7 1
样例1输出
3
样例2输入
8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0
样例2输出
100000000
2 思路
2.1 暴力求解
用vector存储输入的每个y和result值，待全部输入完成后，使用二重循环遍历依次遍历每个元素
- 第一个元素和全部元素（包括第一个元素）比较，当比较的值大于等于第一个元素且result = 1或者 小于第一个元素且result = 0时，预测正确次数加1，
- 每当一个元素比较完全部元素成后，与之前存储的最大预测正确次数比较
- 如果预测正确次数大于之前存储的最大预测正确次数，则更新最大预测正确次数和对应的元素，
- 如果预测正确次数等于之前存储的最大预测正确次数且当前对应的元素也大于之前最大预测正确次数对应的元素，则更新最大预测正确次数和对应的元素，
- 这样一直比较完所有元素后，输出最大预测正确次数对应的元素。
由于进行的双重for循环，时间复杂度为O(m2)，当m特别大如105时，程序会运行超时
2.2 简化
由第一种解法观察发现，计算一个数字对应的预测正确次数 = 到小于当前数字前一个的0的累加和 + （到最大数字为止1的累加和 - 到小于当前数字前一个数字的1的累加和）
例如：
6
0 0
1 0
1 1
3 1
5 1
7 1
对应的解析为
| 数字 | 0的个数 | 1的个数 | 预测正确次数 |
|---|---|---|---|
| 0 | 1 | 0 | 0 + 4 = 4 |
| 1 | 2 | 1 | 1 + (4 - 0) = 5 |
| 3 | 2 | 2 | 2 + (4 - 1) = 5 |
| 5 | 2 | 3 | 2 + (4 - 2) = 4 |
| 7 | 2 | 4 | 2 + (4 - 3) = 1 |
由此得思路为：
- 1，首先用vector存储每个数字对应的0和1的个数，
- 2，然后使用map存储有vector存储的对应的到每个数字截止的0和1的个数，
- 3，遍历map，计算每个数字的预测正确次数，如果当前计算的预测正确次数大于或等于【因为map会自动按非递减的顺序排序，因此无需特殊处理等于的情况】之前存储的最大的预测正确次数，则更新最大的预测正确次数和对应的数字。
- 4 ，输出最大的预测正确次数对应的数字
3 代码
3.1 暴力求解
#include <cstdio>
#include <vector>
int main(){
int m, y, result;
scanf("%d", &m);
std::vector<int> yVec, resVec;
for(int i = 0; i < m;i++){
scanf("%d%d", &y, &result);
yVec.push_back(y);
resVec.push_back(result);
}
int ans = yVec[0], maxCnt = 0;
for(std::vector<int>::iterator i = yVec.begin(); i != yVec.end(); i++){
int tempCnt = 0;
for(int j = 0; j < m; j++){
if((yVec[j] >= (*i) && resVec[j] == 1) || (yVec[j] < (*i) && resVec[j] == 0)){
tempCnt++;
}
}
if((tempCnt > maxCnt) || (tempCnt == maxCnt && (*i) > ans)){
maxCnt = tempCnt;
ans = (*i);
}
}
// for(auto i: yVec){
// int index = 0, tempCnt = 0;
// for(auto y: yVec){
// if((y >= i && resVec[index] == 1) || (y < i && resVec[index] == 0)){
// tempCnt++;
// }
// index++;
// }
// if((tempCnt > maxCnt) || (tempCnt == maxCnt && i > ans)){
// maxCnt = tempCnt;
// ans = i;
// }
// }
printf("%d", ans);
return 0;
}
3.2 简化
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <iterator>
using std::vector;
using std::sort;
using std::map;
using std::advance;
typedef struct Data{
int y, result;
Data(int _y, int _result):y(_y),result(_result){}
Data(){}
}Data;
typedef struct Statistics{
int zeroNum;
int oneNum;
Statistics():zeroNum(0),oneNum(0){}
}Statistics;
bool cmp(const Data& d1, const Data& d2){
if(d1.y < d2.y) return true;
else return false;
}
int main(){
int m, y, result;
vector<Data> data;
scanf("%d", &m);
//存储数值
for (int i = 0; i < m; ++i) {
scanf("%d%d", &y, &result);
data.push_back(Data(y, result));
}
//排序
sort(data.begin(), data.end(), cmp);
//统计截止到每个元素的0和1的个数
map<int, Statistics> mp;
for(int i = 0;i < m;i++){
if(i != 0){
mp[data[i].y].zeroNum = mp[data[i-1].y].zeroNum;
mp[data[i].y].oneNum = mp[data[i - 1].y].oneNum;
}
if(data[i].result == 0){
mp[data[i].y].zeroNum++;
}else{
mp[data[i].y].oneNum++;
}
}
// for(int i = 0;i < m;i++){
// printf("%d zeroNum:%d oneNum:%d\n", data[i].y, mp[data[i].y].zeroNum ,mp[data[i].y].oneNum);
// }
//特殊处理第一个元素，
int ans = data[0].y, maxCnt = mp[data[m -1].y].oneNum, tempCnt = 0;
// printf("%d oneNum:%d\n", data[0].y, mp[data[m -1].y].oneNum);
//使用双指针法，第一个指针iter指向要计算元素的前一个元素，iter2指向当前计算的元素
map<int,Statistics>::iterator iter = mp.begin(), iter2 = mp.begin();
if(mp.size() > 1) advance(iter2, 1);
for(; iter2 != mp.end();iter2++, iter++){
tempCnt = iter->second.zeroNum + (mp[data[m -1].y].oneNum - iter->second.oneNum);
// printf("%d zeroNum:%d oneNum:%d\n", iter2->first, iter->second.zeroNum, (mp[data[m -1].y].oneNum - iter->second.oneNum));
//更新数值
if(tempCnt >= maxCnt){
maxCnt = tempCnt;
ans = iter2->first;
}
}
printf("%d", ans);
return 0;
}
/*
6
0 0
1 0
1 1
3 1
5 1
7 1
*/