本文主要是介绍hdu 4217 Data Structure?(树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：hdu 4217 Data Structure?
题目大意：给出n和m，表示有n个数1~n，然后每次从这个集合中挑选出第ki个小的（m次），问说挑选出来的数字的和。
解题思路：树状数组，v记录的即为其区间上有多少个数未选取，进行取操作的时候只要找到第x个，使得前面的和刚好是ki即可。
#include <stdio.h>
#include <string.h>
#include <iostream>using namespace std;const int N = 270000;
typedef long long ll;int n, m;
ll v[N];void add(int x, int val) {while (x <= n) {v[x] += val;x += (x & (-x));}
}void init() {scanf("%d%d", &n, &m);memset(v, 0, sizeof(v));for (int i = 1; i <= n; i++) add(i, 1);
}int sum(int k) {int x = 0, s = 0;for (int i = 18; i >= 0; i--) {if (x + (1<<i) < n && s + v[x+ (1<<i)] < k) {x += (1<<i);s += v[x];}}return x+1;
}ll solve() {int k;ll ans = 0;for (int i = 0; i < m; i++) {scanf("%d", &k);int s = sum(k);ans += s;add(s, -1);}return ans;
}int main() {int cas;scanf("%d", &cas);for (int i = 1; i <= cas; i++) {init();cout << "Case " << i <<": " << solve() << endl;}return 0;
}
这篇关于hdu 4217 Data Structure?(树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
