傳送門：>Here<

題意：給出長度相等的數(shù)組a和b，定義他們的和為$\dfrac{a_1+a_2+...+a_n}{b_1+b_2+...+b_n}$。現(xiàn)在可以舍棄k對元素（一對即$a[i]和b[i]$），問最大的和是多少？

解題思路

01分?jǐn)?shù)規(guī)劃入門題（并沒有學(xué)過，看到hy大佬在刷因此也去學(xué)了下）

問題可以轉(zhuǎn)化為數(shù)組中的每個(gè)元素選或不選，也就可以認(rèn)為每一個(gè)元素都乘上一個(gè)$x[i], \ x[i] ∈ \{0, 1\}$

因此問題可以轉(zhuǎn)化為$ans = \dfrac{\sum\limits_{i = 1}^{n}a[i] * x[i]}{\sum\limits_{i = 1}^{n}b[i] * x[i]}$

將除法轉(zhuǎn)化為加法$\sum\limits_{i = 1}^{n}a[i] * x[i] - ans * \sum\limits_{i = 1}^{n}b[i] * x[i] = 0$

合并得$\sum\limits_{i = 1}^{n}(a[i]-ans*b[i])*x[i] = 0$

當(dāng)$x$數(shù)組的取值確定時(shí)，可以發(fā)現(xiàn)函數(shù)$f(r) = \sum\limits_{i = 1}^{n}(a[i]-r*b[i])*x[i]$是減函數(shù)，因此可以二分$r$。當(dāng)前取到的$r$能夠滿足$\sum\limits_{i = 1}^{n}(a[i]-r*b[i])*x[i] \geq 0$即為可行，為了滿足此條件，肯定要讓選擇的那些元素的和越大越好，因此可以建立數(shù)組$d[i] = a[i]-r*b[i]$并排序，選擇最大的加起來驗(yàn)證是否大于等于0.

Code

long long

/*By DennyQi 2018.8.12*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define r read() #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) using namespace std; typedef long long ll; #define int long long const int MAXN = 10010; const int MAXM = 27010; const int INF = 1061109567; inline int read(){int x = 0; int w = 1; register int c = getchar();while(c ^ '-' && (c < '0' || c > '9')) c = getchar();if(c == '-') w = -1, c = getchar();while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * w; } struct Score{int idx; double sc; }s[MAXN]; int N,K; int a[MAXN],b[MAXN]; double L,R,Mid,d[MAXN]; inline bool comp(const Score& a, const Score& b){return a.sc < b.sc; } inline bool judge(double _r){for(int i = 1; i <= N; ++i){d[i] = (double)((double)(a[i]) - (double)(1.0*_r*b[i]));}sort(d+1,d+N+1);double res = 0.0;for(int i = N; i > K; --i){res += d[i];}return res >= 0.0; } #undef int int main(){ #define int long longfor(;;){N = r, K = r;if(!N && !K) break;for(int i = 1; i <= N; ++i) a[i] = r;for(int i = 1; i <= N; ++i) b[i] = r;L = 0.000, R = 9999999999.999;while(R - L >= 1e-8){Mid = (L + R) / 2.000;if(judge(Mid)){L = Mid;}else{R = Mid;}}for(int i = 1; i <= N; ++i){s[i] = (Score){i, (double)((double)(a[i]) - (double)(1.0*L*b[i]))};}sort(s+1,s+N+1,comp);int fz=0,fm=0;for(int i = N; i > K; --i){fz += a[s[i].idx];fm += b[s[i].idx];}double rs = (double)fz/(double)fm;printf("%.0f\n", rs * 100);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/qixingzhi/p/9462816.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的[POJ2976] Dropping tests的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。