HDU 1029 Ignatius and the Princess IV (动态规划、思维)
发布时间:2020-12-15 08:25:10 所属栏目:Java 来源:网络整理
导读:Ignatius and the Princess IV Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32767 K (Java/Others) Total Submission(s): 51503????Accepted Submission(s): 23178 ? Problem Description ? "OK,you are not too bad,em... But you can
Ignatius and the Princess IVTime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32767 K (Java/Others) ? Problem Description?
"OK,you are not too bad,em... But you can never pass the next test." feng5166 says.
"I will tell you an odd number N,and then N integers. There will be a special integer among them,you have to tell me which integer is the special one after I tell you all the integers." feng5166 says. "But what is the characteristic of the special integer?" Ignatius asks. "The integer will appear at least (N+1)/2 times. If you can‘t find the right integer,I will kill the Princess,and you will be my dinner,too. Hahahaha....." feng5166 says. Can you find the special integer for Ignatius? ? Input?
The input contains several test cases. Each test case contains two lines. The first line consists of an odd integer N(1<=N<=999999) which indicate the number of the integers feng5166 will tell our hero. The second line contains the N integers. The input is terminated by the end of file.
? Output?
For each test case,you have to output only one line which contains the special number you have found.
? Sample Input5 1 3 2 3 3 11 1 1 1 1 1 5 5 5 5 5 5 7 1 1 1 1 1 1 1 Sample Output3 5 1 题目大意与思路输入一组数,n个,将该组数中相同数字的个数大于(n+1)/ 2 的数字输出。 我是看题目分类来做这个题的,怎么也想不出来动规怎么做 看了别人的题解恍然大悟 真是太高妙了 如果这个数出现次数大于(n+1)/ 2的话 那么他比所有其他的数出现次数都要多! 具体的看代码吧 应该很清楚了 #include<bits/stdc++.h> using namespace std; int i,n,cnt,anss,x; int main() { while(scanf("%d",&n)!=EOF) { cnt=0; for(i=1;i<=n;i++) { cin>>x; if(cnt==0) { cnt++; anss=x; } else { if(x==anss) cnt++; else cnt--; } } cout<<anss<<endl; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
推荐文章
站长推荐
热点阅读