HDU 5873 Football Games（竞赛图兰道定理）

http://acm.hdu.edu.cn/showproblem.php?pid=5873

题意：

现在有比赛，所有队伍两两进行比赛，赢的积2分，输的积0分，如果平局的话就各自都积1分，现在给出每只队伍的得分情况，判断是否合法。

思路：

竞赛图中有关于得分序列这方面的知识，这里引用一下来自http://blog.csdn.net/a_crazy_czy/article/details/73611366博主的讲解。

那么，对于这道题目来说，首先对所有得分排个序，再依次处理即可，前i只队伍的得分情况必须得大于等于$i*(i-1)$，因为每次比赛都会使得总分+2分，而当i=n时，也就是判断到最后一支队伍时，必须要等于$n*（n-1）$。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn=+;

 int n;

 int a[maxn];

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     while(~scanf("%d",&T))

     {

         while(T--)

         {

             bool flag=true;

             scanf("%d",&n);

             for(int i=;i<=n;i++) scanf("%d",&a[i]);

             sort(a+,a+n+);

             int sum=;

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

             {

                 sum+=a[i];

                 if(i<n)

                 {

                     if(sum<i*(i-))  {flag=false;break;}

                 }

                 else

                 {

                     if(sum!=i*(i-))  flag=false;

                 }

             }

             if(flag)  puts("T");

             else puts("F");

         }

     }

     return ;

 }

巴特西

HDU 5873 Football Games（竞赛图兰道定理）

最新文章

热门文章