Submission #69491099

---

Source Code Expand

/* Code By WCM */
/*
Date:
大致思路：
复杂度：
期望得分：
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
#define int long long
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()

using namespace std;

inline int read();
void write(int);
void writeln(int);

typedef double db;
const int N = 1e5 + 5;
int T, n, k, X;
db a[N];

signed main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> T;
	while(T--) {
		cin >> n >> k >> X;
		priority_queue <db> q;
		map <db, int> mp;
		for(int i = 0; i < n; i++) cin >> a[i], mp[a[i]]++, q.push(a[i]);
		while(k > 0) {
			if(q.empty()) break;
			db x = q.top();
			while(mp.find(x) == mp.end() || mp[x] == 0) {
				q.pop();
				if(q.empty()) break;
				x = q.top();
			}
			int ct = mp[x];
			if(ct <= k) mp[x] = 0, mp[x / 2.0] += ct * 2, q.push(x / 2.0), k -= ct;
			else mp[x] -= k, mp[x / 2.0] += k * 2, k = 0;
		}
		vector <pair <db, int> > Q;
		for(auto &x : mp) if(x.S > 0) Q.pb({x.F, x.S});
		sort(all(Q)), reverse(all(Q));
		int now = 0; db ans = 0.0;
		for(auto &x : Q) {
			if(now + x.S >= X) { ans = x.F; break; }
			now += x.S;
		}
		cout << fixed << setprecision(20) << ans << '\n';
	}
	
//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while( !(ch >= '0' && ch <= '9') ) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Judge Result