CodeForces 900C Remove Extra One

题目大意

https://codeforces.com/problemset/problem/900/C

题解

只有满足a[j] > a[i]并且1~i-1的数里面>a[i]的数只有a[j]一个时，删除a[j]才能让records个数增加。 因此可以看出此时在1~i的数里面a[j]是最大的，而且a[i]是次大的，只有这样才能保证删除a[j]时，a[i]成为records。 我们遍历每个数都要维护最大值和次大值，若遍历到的数比最大值大，则更新最大值最小值，同时将新最大值的删除所能增加的records个数设置为-1，因为，最大值本身就是一个records，若删除它相当于-1；若遍历到的数值在最大值和次大值之间，更新次大值，同时让最大值的删除所能增加的records个数+1，因为删除最大值可以让遍历到的当前的数成为records；若遍历到的数比次大值还小，那这个数无法成为records，不进行操作。

代码

#include
using namespace std;
const int N = 1e5+10;
int ans = 1, n, x, mm, m, res[N]; // mm保存最大值，m保存次大值，res[x]表示删除x后能增加多少个records
int main()
{
	cin>>n;
	for(int i = 1;i >x;
		if(x > mm) m = mm, mm = x, res[x] = -1; 
		else if(x > m) res[mm] ++, m = x;
	}
	for(int i = 1;i  res[ans]) 
			ans = i;
	cout