首页 > 代码库 > BZOJ 1303 CQOI 2009 中位数图 模拟
BZOJ 1303 CQOI 2009 中位数图 模拟
题目大意:给出一个1~n的排列,问这其中的中位数为k的子序列的数量是多少。
思路:要想让k为中位数,一定要让它出现在这个序列中所以就以这个数为中心向两边拓展。想让一个数成为中位数,那么这个序列中出现的小于它的数一定要等于大于它的数。考虑到这个数左右都有可能有数字,那么就可以表示成:前多+后多=前少+后少,也就是前多-前少=后少-后多。之后就用个数组随意统计一下就行了。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100010 #define BASE 100001 using namespace std; int points,pos,p; int src[MAX]; int _less[MAX],more[MAX]; int cnt[MAX << 1]; int main() { cin >> points >> p; for(int i = 1; i <= points; ++i) { scanf("%d",&src[i]); if(src[i] == p) pos = i; } ++cnt[BASE]; for(int i = pos - 1; i; --i) { _less[i] = _less[i + 1],more[i] = more[i + 1]; src[i] < p ? ++_less[i]:++more[i]; } for(int i = pos + 1; i <= points; ++i) { _less[i] = _less[i - 1],more[i] = more[i - 1]; src[i] < p? ++_less[i]:++more[i]; ++cnt[BASE + _less[i] - more[i]]; } int ans = 0; for(int i = pos; i; --i) ans += cnt[BASE + more[i] - _less[i]]; cout << ans << endl; return 0; }
BZOJ 1303 CQOI 2009 中位数图 模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。