首页 > 代码库 > 2016 ACM/ICPC Asia Regional Dalian Online

2016 ACM/ICPC Asia Regional Dalian Online

2024-08-12 23:59:32   222人阅读

 

1006　　Football Games

这道题输入也很阴险！！！

这道题过题姿势最优雅的，不是if else if else if。那样很容易wa的。

如果没有平手选项, 赢得加一分的话, 可以用Landau‘s Theorem（兰道定理）判定。 稍微修改一下这个定理就能做了。

假设S1,S2……Sn是他们的得分序列，从小到排个序。那么这个序列要是合法。那么当且仅当

  • S1+S2+……+Sn = n(n-1）
  • S1+S2+……+Si >= i(i-1)  ( 1 <= i < n)

其实第二条也可以理解成，第i大的得分，不可能多于2（i-1）,因为你最多把剩下的队伍全部赢一边。

 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int maxn = 20000 + 5; 5 int T, n; 6 int a[maxn]; 7 void solve() 8 { 9     scanf("%d", &n);10     for(int i = 1; i <= n; i++)11     {12         scanf("%d", &a[i]);13     }14     sort(a + 1, a + n + 1);15     int sum = 0;16 17     for(int i = 1; i <= n; i++)18     {19         sum = sum + a[i];20         if(sum < i * (i - 1))21         {22             printf("F\n");23             return ;24         }25     }26     if(sum != n * (n - 1))27         printf("F\n");28     else29         printf("T\n");30 }31 int main()32 {33     while(~scanf("%d", &T))34     {35         while(T--)36         {37             solve();38         }39     }40     return 0;41 }

 

2016 ACM/ICPC Asia Regional Dalian Online


联系
我们