您现在的位置是:网站首页> 内容页

AtCoder Regular Contest 101 D - Median of Medians

  • 2019-11-05
  • 135人已阅读
简介二分答案然后前缀和+树状数组来判断这个答案是否大于等于数如果我们对于一个查询,如果小于这个数令为1,大于这个数领为-1将所有前缀和放在树状数组中,就可以查询所有sum_{l}<

二分答案

然后前缀和+树状数组来判断这个答案是否大于等于数如果我们对于一个查询,如果小于这个数令为1,大于这个数领为-1将所有前缀和放在树状数组中,就可以查询所有sum_{l} < sum_{r}的组合

#include <assert.h>#include <algorithm>#include <bitset>#include <climits>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <functional>#include <iomanip>#include <iostream>#include <list>#include <map>#include <queue>#include <set>#include <stack>#include <vector>using namespace std;const int N = 1e5 + 5;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;typedef long long ll;int A[N];int B[N];int C[N];ll tree[N * 2];int n;void Add(int pos, int num) { for (int i = pos; i <= 2 * n; i += i & -i) tree[i] += num;}ll Sum(int pos) { ll ans = 0; for (int i = pos; i > 0; i -= i & -i) ans += tree[i]; return ans;}bool solve(int x) { memset(tree, 0, sizeof(tree)); for (int i = 1; i <= n; ++i) { if (A[i] >= x) C[i] = 1; else C[i] = -1; } ll ans = 0; Add(n, 1); for (int i = 1; i <= n; ++i) { C[i] += C[i - 1]; ans += Sum(C[i] + n); Add(C[i] + n, 1); } // printf("%d", ans); return (ans >= (1ll * n * (n + 1) / 4));}int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; ++i) { scanf("%d", &A[i]); B[i] = A[i]; } sort(B + 1, B + n + 1); int tot = unique(B + 1, B + n + 1) - B - 1; int l = 1; int r = tot; while (l <= r) { int mid = (l + r) >> 1; if (solve(B[mid])) l = mid + 1; else r = mid - 1; } // for(int i = 1; i <= tot; ++i) printf("%d ", B[i]); printf(""); printf("%d", B[r]); } return 0;}

文章评论

Top