首页 > 代码库 > 2016 ACM/ICPC Asia Regional Dalian Online
2016 ACM/ICPC Asia Regional Dalian Online
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。