AcWing 3237. 差分 有兴趣可以看看复习一下
原题链接
简单
作者:
段嘉许_
,
2022-12-11 20:52:50
,
所有人可见
,
阅读 159
算法1
(差分) $O(n)$
- q[ ]记录比自己大的数有几个
- s[ ]记录比自己小的数有几个
C++ 代码
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N];
int q[N], s[N]; // q[i]: 比i大的数的个数; s[i]: 比i小的数的个数
void add(int l, int r, int q[])
{
q[l] ++;
q[r + 1] --;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
int x;
cin >> x;
add(0, x - 1, q);
add(x + 1, N - 1, s);
a[i] = x;
}
for(int i = 0; i < N; i ++) if(i) q[i] += q[i - 1], s[i] += s[i - 1];
int res = -1;
for(int i = 0; i < n; i ++) if(q[a[i]] == s[a[i]]) res = a[i];
cout << res << endl;
return 0;
}