Love
-
- 前言
- 题目
- 解法
- CODE
前言
调了两个小时发现是快排的原因以后就比较崩溃，然后开始看RE的原因。一个double的交换变量我写成了int所以就死循环了。
注意好变量类型，一步步的排除问题要高效一点。不要盲目去排查，不然像这次两小时就没了。
题目
Description
鸡腿是CZYZ的著名DS，但是不想追妹子的DS不是好GFS，所以鸡腿想通过表白来达到他追到妹子的目的！虽然你对鸡腿很无语，但是故事的设定是你帮助鸡腿找到了妹子，所以现在你必须帮助鸡腿安排表白来实现故事的结局 ！
鸡腿想到了一个很高（sha）明（bi）的做法，那就是去找人来组成表白队伍来增强气势 ！鸡腿有很多好基友来帮忙，鸡腿数了数一共有N个人。但是鸡腿觉得大家排成两队来比较好看，而且鸡腿经过计算，第一队N1个人，第二队N2个人是最佳的队伍。问题来了…有些好基友们虽然很好心但是可能造成不好的影响（形象猥琐），所以鸡腿就给每个人打了分。Q1i表示第i个好基友排到第一队里时的好影响，C1i表示第i个好基友排到第一队里时的不良影响，Q2i表示第i个好基友排到第二队里时的好影响，C2i表示第i个好基友排到第二队里时的不良影响。请给鸡腿一种安排使得Q的和与C的和的比值最大，给出最大值。
Input
第一行给出三个整数N、N1、N2。
第2到N+1行，每行四个整数Q1,C1,Q2,C2。
Output
一行输出一个小数d表示最优化比例是d（保留6位小数）
Sample Input
5 2 2
12 5 8 3
9 4 9 4
7 3 16 6
11 5 7 5
18 10 6 3
Sample Output
2.444444
Data Constraint
对于50%的数据0 < N1 + N2 ≤ N ≤ 50；
对于100%的数据0 < N1 + N2 ≤ N ≤ 500，1 ≤ Q1, Q2 ≤ 2000，1 ≤ C1, C2 ≤ 50。
解法
首先明确01分数规划。
那么我们就可以用到二分答案，所以一个mid要成立，就要成立下列不等式。
由题意得： ∑ x ∈ f i r s t g r o u p ( q 1 i − c 1 i ∗ k ) − ∑ x ∈ s e c o n d g r o u p ( q 2 i − c 2 i ∗ k ) ≥ 0 ∑x∈firstgroup(q1i−c1i∗k)-∑x∈ secondgroup(q2i−c2i∗k)≥0 ∑x∈firstgroup(q1i−c1i∗k)−∑x∈secondgroup(q2i−c2i∗k)≥0
因为是减号，要使得这个值最大，就前面最大，后面最小。
考虑DP
因为要前面的最大，所以其实可以排一下序。从大到小。
设： F i , j F_{i,j} Fi,j表示从前到i选了j个的最大值。
G i , j G_{i,j} Gi,j表示从后到i选了j个的最大值。
那么F数组必定是最大的，G数组是最小的。
然后找出最大的f[i][n1]+g[n-i][n2]，判断正负即可。
CODE
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define N 505
#define inf 1000000007
#define ri register int
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,n1,n2;
int sum=0,kk;
double a[N],q1[N],c1[N],q2[N],c2[N],q3[N],c3[N],q4[N],c4[N],ls;
double f[N][N],g[N][N];
inline int read()
{
int re=0,ra=1;
char str=getchar();
while(str>'9'||str<'0'){str=getchar();if(str=='-') ra=-1;}
while(str>='0'&&str<='9')re=(re<<1)+(re<<3)+str-'0',str=getchar();
return re*ra;
}
void qsort(int p,int q)
{
int i=p,j=q;
double mi=a[(p+q)/2];
while(i<=j)
{
while(a[i]>mi) i++;while(a[j]<mi) j--;
if(i<=j) swap(a[i],a[j]),swap(q3[i],q3[j]),swap(c3[i],c3[j]),swap(q4[i],q4[j]),swap(c4[i],c4[j]),i++,j--;
}if(i<q) qsort(i,q);if(p<j) qsort(p,j);
}
bool check(double t)
{
sum++;
memset(f,-inf,sizeof(f)),memset(g,-inf,sizeof(g));
for(ri i=1;i<=n;++i) q3[i]=q1[i],c3[i]=c1[i],q4[i]=q2[i],c4[i]=c2[i];
for(ri i=1;i<=n;++i) a[i]=(q3[i]-t*c3[i])-(q4[i]-t*c4[i]);
qsort(1,n);
f[1][1]=q3[1]-c3[1]*t,f[1][0]=0;
for(ri i=2;i<=n;++i)
for(ri j=0;j<=min(i,n1);++j)
f[i][j]=max(f[i-1][j],f[i-1][j-1]+q3[i]-c3[i]*t);
g[1][1]=q4[n]-c4[n]*t,g[1][0]=0;
for(ri i=2;i<=n;++i)
for(ri j=0;j<=min(i,n2);++j)
g[i][j]=max(g[i-1][j],g[i-1][j-1]+q4[n-i+1]-c4[n-i+1]*t);
ls=-1000;
for(ri i=1;i<=n;++i)
if(i>=n1&&n-i>=n2)
if(f[i][n1]+g[n-i][n2]>ls)
ls=f[i][n1]+g[n-i][n2];
if(ls>=0) return true;return false;
}
int main()
{
fre(love);
n=read(),n1=read(),n2=read();
for(ri i=1;i<=n;++i) q1[i]=read(),c1[i]=read(),q2[i]=read(),c2[i]=read();
double l=0,r=2000.0,mid;
while(r-l>=0.0000000001)
{
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.6lf",mid);
return 0;
}