题解 P3068 【[USACO13JAN]派对邀请函Party Invitations】

xiaozeyu · 2019-10-26 13:20:10 · 题解

既然不好写就换一个思路

这道题如果按每一小块直接算，既麻烦又费时，所以我们可以转换一下思路

我们可以把所有的数据接到一起，用一个算前缀和的数组进行标号，在每一次循环有效的处理每一组数据

#include<bits/stdc++.h>
using namespace std;
int n,g,sum[2050],t[2050],a[250005],ans=1;
bool f[250005];//定义
int main()
{
    f[1]=1;
    scanf("%d%d",&n,&g);
    for(int i=1;i<=g;i++)
    {
        scanf("%d",&t[i]);//输入每组大小
        sum[i]=sum[i-1]+t[i];//记录总数
        for(int j=sum[i-1]+1;j<=sum[i];j++)
            scanf("%d",&a[j]);//在每一小段输入每个
    }
    while(1)//多次循环一直找
    {
        int k=ans;//继承上一次循环结果
        for(int i=1;i<=g;i++)
        {
            int q,s=0;//清零
            for(int j=sum[i-1]+1;j<=sum[i];j++)//枚举每一段
            {
                if(f[a[j]])//是否参加
                    s++;
                else 
                    q=a[j];//标记
            }   
            if(t[i]-s==1)//至少k-1个奶牛参加派对时，必须邀请最后的一头奶牛
            {
                f[q]=1;//参加
                ans++;//总数加上这个
            }
        }
        if(k==ans)//两次循环结果不再变化，则已最优
        {
            cout<<ans;//输出
            return 0;
        }
    }
}