No Girlfriend(簡単な問題)
1906 ワード
1、http://acm.nbut.edu.cn/Problem/view.xhtml?id=1543
2、テーマの大意
バレンタインデーが近づいて、n人がそれぞれ自分の好きな人とデートして、一人一人のデートの人の番号を与えて、もしその中の一人を連れて行くならば、その人が好きな人たちは楽しくなくて、今あなたは一人を連れて行って、楽しくない人数を最も多くします
簡単な問題ですが、あまりにも焦って、境界に注意しないで提出して、wrongは2回やっとACを招きました
3、テーマ:
[C] No Girlfriend
時間制限:2000 msメモリ制限:262144 K 問題の説明You know the day after tomorrow is Valentine's Day, but I have no girlfriend.
Now, I'll give you a big task, help me take away a person!
If you take away that person, others who want to appointment with him/her will feel disappointed.
Your task is to let maximum people feel disappointed.
入力There are multiple test cases, each test case contain a positive number N (1 <= N <= 100).
Following N lines, for the ith line (1-Based) contain a positive integer P (1 <= P <= N), represent the ith people want to appointment with P.
Note: Everyone has a distinct number, the ith people's number is i.
出力For each case, output the answer in one line.
サンプル入力
サンプル出力
ヒント
2、テーマの大意
バレンタインデーが近づいて、n人がそれぞれ自分の好きな人とデートして、一人一人のデートの人の番号を与えて、もしその中の一人を連れて行くならば、その人が好きな人たちは楽しくなくて、今あなたは一人を連れて行って、楽しくない人数を最も多くします
簡単な問題ですが、あまりにも焦って、境界に注意しないで提出して、wrongは2回やっとACを招きました
3、テーマ:
[C] No Girlfriend
時間制限:2000 msメモリ制限:262144 K 問題の説明You know the day after tomorrow is Valentine's Day, but I have no girlfriend.
Now, I'll give you a big task, help me take away a person!
If you take away that person, others who want to appointment with him/her will feel disappointed.
Your task is to let maximum people feel disappointed.
入力There are multiple test cases, each test case contain a positive number N (1 <= N <= 100).
Following N lines, for the ith line (1-Based) contain a positive integer P (1 <= P <= N), represent the ith people want to appointment with P.
Note: Everyone has a distinct number, the ith people's number is i.
出力For each case, output the answer in one line.
サンプル入力
3311555222
サンプル出力
23
ヒント
For the first test case.If you take away 1, then 2 and 3 will feel disappointed.If you take away 2, nobody will feel disappointed.If you take away 3, then 1 will feel disappointed.So the maximum people feel disappointed is 2.
4、ACコード:#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int b[105];
int cmp(int c,int d)
{
return c>d;
}
int main()
{
int n,a;
while(scanf("%d",&n)!=EOF)
{
memset(b,0,sizeof(b));
for(int i=0;i<n;i++)
{
scanf("%d",&a);
b[a]++;
}
sort(b,b+n+1,cmp);
printf("%d
",b[0]);
}
return 0;
}