国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > UVA1428 - Ping pong(树状数组)

UVA1428 - Ping pong(树状数组)

来源:程序员人生   发布时间:2014-10-04 08:00:01 阅读次数:2205次

UVA1428 - Ping pong(树状数组)

题目链接

题目大意:有N个人,每个人都有一个技能值ai,现在要开展乒乓球比赛,要求要有两个选手和一个裁判,要求裁判需要在两名选手的中间而且技能值也是在两名选手的中间,问可以开展多少场比赛。

解题思路:对于第i个选手当裁判的话,设它前面位置的选手有ci个技能值比它低的,那么就有i - 1 - ci个比它高的,对于第i选手后面的位置,同样有di个技能值比它低的,那么就有N - i - di个比它高的。组合一下:ci?(N - i - di) + (i - 1 - ci) ? di.那么对于ci的值,根据i的位置,将Xi标为0或者1(在i位置前面就是1,后面就是0)。di类似求得。

代码:

#include <cstdio> #include <cstring> const int maxn = 1e5 + 5; const int N = 2e4 + 5; typedef long long ll; int C[maxn]; int A[maxn]; ll c[N], d[N]; int lowbit(int x) { return x&-x; } void Add (int x, int d) { while (x < maxn) { C[x] += d; x += lowbit(x); } } int Sum (int x) { int ret = 0; while (x > 0) { ret += C[x]; x -= lowbit(x); } return ret; } void init () { memset (C, 0, sizeof (C)); } int main () { int T; int n; int num[N]; scanf ("%d", &T); while (T--) { scanf ("%d", &n); init(); for (int i = 0; i < n; i++) { scanf ("%d", &num[i]); Add(num[i], 1); c[i] = Sum (num[i]) - 1; } init(); for (int i = n - 1; i >= 0; i--) { Add(num[i], 1); d[i] = Sum (num[i]) - 1; } ll ans = 0; for (int i = 0; i < n; i++) { // printf ("%lld %lld ", c[i], d[i]); ans += c[i] * (n - i - 1 - d[i]) + (i - c[i]) * d[i]; } printf ("%lld ", ans); } return 0; }
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生