C.数组平均
游游拿到了一个大小为n的数组，数组第i个数为a_i。
游游可以选择一些元素，使得这些元素都等于它们的平均数。
eg.假设数组为 [5, 4, 2, 4]，游游选择第一个和第三个元素，最终数组将变成 [3.5, 4, 3.5,4]
游游最多可以选择k个元素，她希望最终数组最大值和最小值的差尽可能小。你能帮她求出这个差吗？
贪心+前缀和
可以发现选中的元素个数越多，数组的max - min 的差值越小，同时维护前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| double a[200005];
double b[200005];
void solve(){
int n = read(), k = read();
for(int i = 1; i <= n; ++ i){
cin >> a[i];
}
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; ++ i){
b[i] = b[i - 1] + a[i];
}
double ans = 1e9;
for(int i = 0; i <= k; ++ i){
int j = k - i;
double ave = (b[i] + b[n] - b[n - j]) / k;
double mi = min(a[i + 1], ave);
double ma = max(a[n - j], ave);
ans = min(ans, ma - mi);
}
printf("%.7lf", ans);
}
|
D.游游出游
游游准备去开车旅行，她初始在1号城市，准备前往n号城市。
游游打开了携程，她查询到了地图上有若干城市，城市之间有一些道路连接。每条道路有承重限制，当游游的车重量超过了承重时，她就不能走这条道路。游游是一个贪心的人，她希望总路程不超过h的前提下，携带尽可能多的物品出行。游游想知道，自己的车最多重量能达到多少？
二分 + dijkstra 二分最大的答案的同时 通过跑最短路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| typedef struct node{
int v, w, d;
}node;
void solve(){
int n = read(), m = read(), h = read();
vector<vector<node>> g(n + 1);
vector<int> dist(n + 1);
vector<int> st(n + 1);
for(int i = 0; i < m; ++ i){
int u = read(), v = read(), w = read(), d = read();
g[u].push_back({v, w, d});
g[v].push_back({u, w, d});
}
function<int(int)> check = [&](int mid) -> bool{
priority_queue<PII, vector<PII>, greater<PII> > q;
q.push({0, 1});
for(int i = 1; i <= n; ++ i) st[i] = 0, dist[i] = 0x3f3f3f3f;
dist[1] = 0;
while(q.size()){
PII t = q.top();
q.pop();
int distance = t.first, ver = t.second;
if(st[ver]) continue;
st[ver] = 1;
for(node &it : g[ver]){
if(mid > it.w){
continue;
}
if(dist[it.v] > dist[ver] + it.d){
dist[it.v] = dist[ver] + it.d;
q.push({dist[it.v], it.v});
}
}
}
return dist[n] <= h;
};
int l = 0, r = 1e9;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)){
l = mid;
}
else{
r = mid - 1;
}
}
if(!check(l)) cout << "-1";
else cout << l;
}
|