[USACO14MAR] Counting Friends
题目描述
Farmer John's N cows (2 <= N <= 500) have joined the social network "MooBook".
Each cow has one or more friends with whom they interact on MooBook. Just for fun, Farmer John makes a list of the number of friends for each of his cows, but during the process of writing the list he becomes distracted, and he includes one extra number by mistake (so his list contains N+1 numbers, instead of N numbers as he intended).
Please help Farmer John figure out which numbers on his list could have been the erroneous extra number.
FJ又有n(1<=n<=500)头奶牛都有一个或一个以上的朋友。FJ记录每头牛的朋友数,但他傻不小心混入了一个错的数字,请找出。
输入输出格式
输入格式:
Line 1: The integer N.
- Lines 2..2+N: Line i+1 contains the number of friends for one of FJ's cows, or possibly the extra erroneous number.
输出格式:
Line 1: An integer K giving the number of entries in FJ's list that could be the extra number (or, K=0 means that there is no number on the list whose removal yields a feasible pairing of friends).
- Lines 2..1+K: Each line contains the index (1..N+1) within the input ordering of a number of FJ's list that could potentially be the extra number -- that is, a number that can be removed such that the remaining N numbers admit a feasible set of
friendships among the cows. These lines should be in sorted order.
输入输出样例
4
1
2
2
1
3
3
1
4
5
说明
Farmer John has 4 cows. Two cows have only 1 friend each, two cows have 2 friends each, and 1 cow has 3 friends (of course, one of these numbers is extra and does not belong on the list).
Removal of the first number in FJ's list (the number 1) gives a remaining list of 2,2,1,3, which does lead to a feasible friendship pairing -- for example, if we name the cows A..D, then the pairings (A,B), (A,C), (A,D), and (B,C) suffice, since A has 3 friends, B and C have 2 friends, and D has 1 friend. Similarly, removing the other "1" from FJ's list also works, and so does removing the "3" from FJ's list. Removal of either "2" from FJ's list does not work -- we can see this by the fact that the sum of the remaining numbers is odd, which clearly prohibits us from finding a feasible pairing.
如果删除这个数合法,
那么按朋友数从大到小排序后,
枚举每个人,枚举它的朋友,
朋友数都减1,最后所有人的朋友数都减为0
注意每轮删减之后都要重新排序
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[],b[],ans[];
int read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
}
int main()
{
int n,cnt;
bool ok;
read(n);
for(int i=;i<=n+;i++) read(a[i]);
for(int i=;i<=n+;i++)
{
ok=true; cnt=;
for(int j=;j<=n+;j++)
if(j!=i) b[++cnt]=a[j];
for(int j=;j<=n+;j++)
{
sort(b+,b+cnt+,greater<int>());
for(int k=;k<=n+ && b[];k++)
{
if(!b[k]) { ok=false; break; }
b[]--; b[k]--;
}
if(b[])
{
ok=false;
break;
}
}
if(ok) ans[++ans[]]=i;
}
printf("%d\n",ans[]);
sort(ans+,ans+ans[]+);
for(int i=;i<=ans[];i++) printf("%d\n",ans[i]); }
最新文章
- RedisRepository封装—Redis发布订阅以及StackExchange.Redis中的使用
- easyUI的基础布局
- Android开发之《常用工具及文档汇总》
- MySql索引简介
- 正则表达式之IP地址检验
- 关于SQL Server的WITH(NOLOCK)和(NOLOCK)
- intellij idea exclude from compile后怎么加回来
- android 组合控件接收不到点击事件的问题
- Part 98 Anonymous methods in c#
- hdu&#160;1162&#160;Eddy&#39;s&#160;picture(最小生成树,基础)
- 转载:java保留2位小数
- python学习笔记--基础语法
- Linux挂载U盘
- Unix/Linux环境C编程入门教程(20) 搭建基于Mac的 Xcode 与 QT 开发环境
- BZOJ 1269: [AHOI2006]文本编辑器editor( splay )
- Python快捷键
- 高效、易用、功能强大的 api 管理平台
- SPREAD for Windows Forms 下箭头追加行
- java常用功能
- [Java中实现国际化] - 配合thymeleaf实现中英文自动切换(多语言)