傳送門：
K Best
題意：
平均值定義為 sum(Vi) / sum(Wi) ，任意選Ｋ組，使得平均值最大。
思路：
為什麼不能用單個 v/w 來當 key 值 greedy 解，這邊不解釋了，我們只需要記得，這類題目先把公式拿來玩一玩！
假設已經知道平均值為 Ａ，則
sum(Vi) / sum(Wi) = A
sum(Vi) = A x sum(Wi) = sum(Wi x A)
sum(Vi) - sum(Wi x A) = 0
sum(Vi - Wi x A) = 0
換句話說，如果要決定這些平均值是否能大於等於Ａ，只需要使用上方最後一個算式，判斷加總後是否大於等於零即可。
再進一步說我們可以將所有v w對依照 V - W x A 排序，之後取前Ｋ大加總即可！
之後我們就能使用上方結論來二分搜平均值，需要注意的是前Ｋ大可以用 nth_element 來實作即可，方便又高效！
還有二分搜的上界好好估，就能節省更多時間，以免ＴＬＥ！ (這題真的很容易TLE呢～)
code:
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
int N,K;
int v[100005], w[100005];
int vt[100005], wt[100005];
double eps = 1e-4;
pii sorting[100005];
void init(){
N = getint(), K = getint();
for(int i=0;i<N;i++)
vt[i] = v[i] = getint(), wt[i] = w[i] = getint(); // v, w
}
inline void trick_sort(){
nth_element(sorting, sorting+K, sorting+N, greater<pii>());
}
inline bool suc(double x){
double cnt = 0;
for(int i=0;i<N;i++)
sorting[i] = MP(- x*w[i] + v[i],i);
trick_sort();
for(int i=0;i<K;i++)
cnt += sorting[i].X;
return cnt>=-eps;
}
inline double trick(){
ll cnt1 = 0, cnt2 = 0;
nth_element(vt, vt+K, vt+N, greater<int>());
nth_element(wt, wt+K, wt+N);
for(int i=0;i<K;i++)
cnt1 += vt[i], cnt2 +=wt[i];
return (double)cnt1 / cnt2;
}
void sol(){
double L = 0, R = trick();
#define mid ((L+R)/2)
while(R-L>eps) suc(mid) ? L=mid : R=mid;
suc(L);
for(int i=0;i<K;i++){
printf("%d", sorting[i].Y+1);
if(i+1<K) printf(" ");
else puts("");
}
}
int main(){
init();
sol();
}