P4653 [CEOI2017] Sure Bet

JFLS_lixiang · 2022-08-30 10:24:18 · 个人记录

预处理：

首先将两个序列分别存在a和b,根据贪心原理，分别从大到小排序，并计算出前缀和sa和sb。

比较

建立两个指针pa=0,pb=0;我们来比较两个序列最小的收益即：sa[pa]-(double)(pa+pb)，sb[pb]-(double)(pa+pb),哪个小，我就让哪个指针++增加收益。时刻维护最小收益值的那个最大值就可以了。代码简短。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
double a[101000],b[101000];
double sa[101000],sb[101000];
int cmp(double a,double b)
{
    return a>b;
}
double ansmax=0,minn=1000000000.0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i]>>b[i];
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;i++)sa[i]=sa[i-1]+a[i],sb[i]=sb[i-1]+b[i];
    int pa=0,pb=0;
    while(pa<=n&&pb<=n)
    {
        if(sa[pa]-(double)(pa+pb)>=sb[pb]-(double)(pa+pb))pb++;
        else pa++;
        minn=min(sa[pa]-(double)(pa+pb),sb[pb]-(double)(pa+pb));
        ansmax=max(minn,ansmax);
    }
    printf("%.4lf",ansmax);
    return 0;
}