D. Martial Arts Tournament

#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 10;

int a[N], c[N];
int n;

int calc (int tar) {
	int j = 0;
	while((1 << j) < tar) j ++;
	return (1 << j) - tar;
}
 
int get (int x, int y) {
	return calc(c[x - 1]) +  calc (c[y - 1] - c[x - 1]) + calc(c[n] - c[y - 1]);
}

int main () {
    int t;
    cin >> t;
     while (t --) {
    	cin >> n;
        memset(c, 0, sizeof c);	
    	for (int i = 1; i <= n; i++) {
    		int t;	cin >> t; c[t] ++;
    	}
    	for (int i = 1; i <= n; i ++) c[i] += c[i - 1]; 
    	int res = 0x3f3f3f3f;
    	for (int x = 1; x <= n + 1; x ++) {
    		int cur = c[x - 1];
    		for (int j = 0; (1 << j) <= n - cur; j ++ ) {
    			int pos = upper_bound(c + 1, c + 1 + n, cur + (1 << j)) - c;
    			res = min (res, get(x, pos));
    // 			pos = lower_bound(c + 1, c + 1 + n, n - (1 << j)) - c + 1;
    // 			res = min (res, get(x, pos));
    		}
    	}
    	cout << res << endl;    
    }
	return 0;
}

log枚举优化然后用枚举每个数。

最后

以上就是幸福鸭子为你收集整理的D. Martial Arts Tournament的全部内容，希望文章能够帮你解决D. Martial Arts Tournament所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。