題意：p， q，都是整數.

sigma（A_{i *}?k_i）>= p,

sigma(B_i?* k_i) >= q;

ans = sigma(k_i)。輸出ans的最小值

約束條件2個，但是變量k有100000個，所以可以利用對偶性轉化為求解

ans = p * y1 + q * y2

約束條件為：

A_i * y1 + B_i * y2 <= 1 其中i為0~n-1

也就是n個約束條件。 后面三分搞搞就好了

?

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5 + 5; 4 double A[maxn], B[maxn], p, q; 5 int n; 6 double check(double x){ 7 double y = 1e20; 8 for (int i = 0; i < n; i++){ 9 y = min(y, (1-A[i]*x)/B[i]); 10 } 11 return p * x + y * q; 12 } 13 int main() 14 { 15 #ifndef ONLINE_JUDGE 16 freopen("in.txt","r",stdin); 17 #endif 18 while (~scanf("%d%lf%lf", &n, &p, &q)){ 19 for (int i = 0; i < n; i++){ 20 scanf("%lf%lf", A+i, B+i); 21 } 22 double l = 0, r = 1.0/(*max_element(A, A+n)); 23 for (int i = 0; i < 250; i++){ 24 double ml = (l + l + r) / 3; 25 double mr = (r + r + l) / 3; 26 if (check(ml) > check(mr)){ 27 r = mr; 28 }else{ 29 l = ml; 30 } 31 } 32 printf("%.20f\n", check((l+l)/2)); 33 } 34 return 0; 35 }

?

轉載于:https://www.cnblogs.com/oneshot/p/5052785.html

總結

以上是生活随笔為你收集整理的Codeforces Round #335 (Div. 1)--C. Freelancer's Dreams 线性规划对偶问题+三分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。