洛谷P2577 午餐

题意概述：有n个人，第i个人打饭消耗ai时间，离开后吃饭耗费bi时间，将n个人分成两队，合理分配人员使总时间最短并输出总时间。

　　我们把问题拆分为两个部分。首先是排列顺序，然后是怎么分到两个队伍中。

　　显然吃饭越慢应该越早打饭，因为打饭总时间不变那么让吃的慢的人早开始吃会使总时间最小。

　　那么现在我们只需要分一下人就好了。看一眼数据发现n<=200，可以使用随机分配。

　　时间复杂度：O(跑的出来)

#include<cstring>

#include<iostream>

#include<cctype>

#include<cstdio>

#include<algorithm>

#include<ctime>

using namespace std;

inline int read()

{

    register int X=;register char ch=;bool flag=;

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') flag=;

    for(;isdigit(ch);ch=getchar()) X=(X<<)+(X<<)+ch-'';

    return (flag ? -X : X);

}

inline void write(int x)

{

     if(x>) write(x/);

     putchar(x%+'');

}

int n;

struct person

{

    int eat,get;

}p[];

int ans=;

int f[];

bool cmp(person xx,person yy){return xx.eat>yy.eat;}

int max(int a,int b){return a>b ? a : b;}

int min(int a,int b){return a>b ? b : a;}

int main()

{

    n=read();

    for(int i=;i<=n;i++)

        p[i].get=read(),p[i].eat=read();

    sort(p+,p+n+,cmp);

    for(int i=;i<=;i++)

        f[i]=(i& ?  : );

    while(clock()<)

    {

        random_shuffle(f+,f+);

        int sum1=,sum2=,tot1=-,tot2=-;

        for(int j=;j<=n;j++)

        {

            if(f[j] & )

                sum1+=p[j].get,tot1=max(tot1,sum1+p[j].eat);

            else

                sum2+=p[j].get,tot2=max(tot2,sum2+p[j].eat);

            if(tot1 > ans || tot2 > ans) break;

        }

        ans=min(ans,max(tot1,tot2));

    }

    printf("%d\n",ans);

}

巴特西

洛谷P2577 午餐

最新文章

热门文章