Codeforces Round #335 (Div. 1)--C. Freelancer's Dreams 线性规划对偶问题+三分

题意：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 线性规划对偶问题+三分的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。