UVA 10273

我是用暴力过的，虽然网上说刘汝佳出的这道题考的是堆，我不太懂，。。用暴力时间复杂度高一些，但是一样能过

所要注意的就是周期问题，因为只要同时存在某一天超过一头牛产奶量最小，就不会杀牛，而每头牛的周期和每天产奶量都不一样，我一开始用周期最长的做指标，如果超过这个指标还没有牛被杀，说明状态稳定，输出。。。但是这样是WA的。。。

正确的周期应该是所有牛的周期的最小公倍数（也可以超过最小公倍数，但无疑最小公倍数是最优的），这也给了我一些新启发，周期不同的时候把所有可能性都走完，就是最小公倍数

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

struct node

{

    int d[];

    int t,cnt;

} cow[];

int gcd(int a,int b)

{

    if (b==) return a;

    else

        return gcd(b,a%b);

}

int eat[];

int n,maxn,day,ans;

void solve()

{

    ans=day=;

    int cur=;

    while ()

    {

        int mini=<<,loc,counts=;

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

        {

            if (eat[i]) continue;

            if (cow[i].d[cow[i].cnt]<mini)

            {

                mini=cow[i].d[cow[i].cnt];

                loc=i;

                counts=;

            }

            else if (cow[i].d[cow[i].cnt]==mini)

            {

                counts++;

            }

            cow[i].cnt=(cow[i].cnt+)%cow[i].t;

        }

        day++;

        cur++;

        //cout<<day<<" "<<loc<<endl;

        //cout<<"maxn "<<maxn<<endl;

        if (counts==)

        {

            eat[loc]=;

            cur=;

            ans=day;

        }

        else if (cur>maxn) break;

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    while (t--)

    {

        scanf("%d",&n);

        maxn=;

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

        {

            scanf("%d",&cow[i].t);

            eat[i]=;

            cow[i].cnt=;

            for (int j=; j<cow[i].t; j++)

                scanf("%d",&cow[i].d[j]);

            if (maxn<cow[i].t)

                {

                    int temp;

                    temp=gcd(cow[i].t,maxn);

                    maxn=maxn*cow[i].t/temp;

                }

                else

                {

                    int temp;

                    temp=gcd(maxn,cow[i].t);

                    maxn=maxn*cow[i].t/temp;

                }

        }

        //out<<maxn<<endl;

        solve();

        int num=;

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

        {

            if (!eat[i]) num++;

        }

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

    }

    return ;

}

巴特西

UVA 10273

最新文章

热门文章