[大数据]202012-2期末预测之最佳阈值

题目

抽象

前缀和与后缀和的问题

分析

• 本题容易想到双重循环进行暴力求解，但是O(n^2)时间复杂度无法适用大数据量，本题数据范围是10 ^5，n ^2就是10 ^10，在这里必须条件反射地想到时间会超过1s，只能得70分，暴力求解在这里并不完美。
• 采用前缀和后缀和思想，可以降低时间复杂度，拿到100分：
  具体为：先对y[i]升序排序，然后记录小于y[i]的0的个数以及大于y[i]的1的个数（前缀和与后缀和），然后经过操作容易求得结果

完整代码

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

pair<int, int> a[100001];
int m, i, prefix[100002], suffix[100002], pos[100001], cnt[100001], maxcnt = cnt[1], theta = a[1].first;

int main()
{
	cin >> m;
	for(i=1; i<=m; i++)
		cin >> a[i].first >> a[i].second;
		
	sort(a+1, a+1+m);//pair默认对first升序，若first相同，对second升序 
	
	//关键一步：为了后面的计算 
	pos[0] = 0;
	a[0].first = -1;
	a[0].second = -1; 
	for(i=1; i<=m; i++)
	{
		pos[i] = 0;
		if(a[i].first == a[i-1].first)
			pos[i] = pos[i] + pos[i-1] - 1;
	}
	
	//求前缀和
	prefix[0] = 0;
	for(i=1; i<=m; i++)
		prefix[i] = prefix[i-1] + (a[i].second == 0 ? 1:0);
		
	//求后缀和
	suffix[100001] = 0;
	for(i=m; i>=1; i--)
		suffix[i] = suffix[i+1] + (a[i].second == 1 ? 1:0);
		 
	for(i=1; i<=m; i++)
	{
		if(a[i].second == 0)
			cnt[i] = prefix[i] - 1 + suffix[i];
		else
			cnt[i] = prefix[i] + suffix[i];
	}
	
	for(i=2; i<=m; i++)
	{
		if(cnt[i+pos[i]] >= maxcnt)
		{
			maxcnt = cnt[i+pos[i]];
			theta = a[i].first;
		}
	}
	
	cout << theta << endl;
	
	return 0;
}

小知识

• 为什么在函数里无法申请很大的数组？
  答:
  因为全局变量是存储在静态存储区分配的，这个空间很大
  局部变量是在栈空间上分配的，栈空间没那么大，太大了会溢出
  所以，写题时定义变量时尽量使用全局变量以防万一。

• pair用法

• vector用法