首页 > 代码库 > [BZOJ 1303] [CQOI2009] 中位数图 【0.0】
[BZOJ 1303] [CQOI2009] 中位数图 【0.0】
题目链接：BZOJ - 1303
题目分析
首先，找到 b 的位置 Pos， 然后将数列中小于 b 的值赋为 -1 ，大于 b 的值赋为 1 。
从 b 向左扩展，不断算 Sum[i, b - 1] ，然后将 Cnt[Sum[i, b - 1]] 加一，这样就算出每个左边的Sum值有多少个了。
然后从 b 向右扩展，不断算 Sum[b + 1, i] ，然后 Ans += Cnt[Sum[b + 1, i]] 。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm> using namespace std; const int MaxN = 100000 + 5; int n, b, num, Pos, Sum;int A[MaxN], CntL[MaxN * 2]; typedef long long LL; LL Ans; int main(){ scanf("%d%d", &n, &b); for (int i = 1; i <= n; ++i) { scanf("%d", &num); if (num == b) { A[i] = 0; Pos = i; continue; } if (num < b) A[i] = -1; else A[i] = 1; } Sum = 0; for (int i = Pos; i >= 1; --i) { Sum += A[i]; ++CntL[Sum + n]; } Sum = 0; Ans = 0ll; for (int i = Pos; i <= n; ++i) { Sum += A[i]; Ans += (LL)CntL[-Sum + n]; } printf("%lld\n", Ans); return 0;}
[BZOJ 1303] [CQOI2009] 中位数图 【0.0】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。