기본 dp
"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 Input
5
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 Output
3
5
1
사고방식: 간단한 dp문제인데 관건은 출현 횟수>(n+1)/2라는 조건을 잘 사용하는 데 있다. 구체적인 코드는 다음과 같다.
코드:
#include
using namespace std;
int main()
{
int n, num, cnt, ans;
while(scanf("%d", &n)!=EOF)
{
cnt = 0;
for(int i=0; i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDOJ3785_계속 xxx 의 법칙계속 xxx 의 법칙 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 129...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.