[ACM]hdu 1205 사탕 먹 기(비둘기 둥지 원리)

사탕 을 먹다
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 21695 Accepted Submission(s): 6185
Problem Description

HOHO,드디어 Speakless 의 손 에서 모든 사탕 을 이 겼 습 니 다.Gardon 이 사탕 을 먹 을 때 특별한 취미 가 있 습 니 다.바로 똑 같은 사탕 을 같이 먹 는 것 을 좋아 하지 않 습 니 다.먼저 하 나 를 먹고 다음 에 다른 것 을 먹 는 것 을 좋아 합 니 다.이렇게 합 니 다.그런데 Gardon 은 사탕 을 다 먹 을 수 있 는 순서 가 있 는 지 모 르 겠 어 요.당신 이 프로그램 을 써 서 계산 하 는 것 을 도와 주세요.

Input

첫 번 째 줄 은 정수 T 가 있 고 그 다음 에 T 조 의 데 이 터 는 각 조 의 데이터 가 2 줄 을 차지 하 며 첫 번 째 줄 은 하나의 정수 N(0

Output

각 그룹의 데이터 에 대해 한 줄 을 출력 합 니 다.'Yes'나'No'를 포함 합 니 다.

Sample Input

Sample Output


   
   
   
   
    
    
    
    No
Yes


    
    
    
     
      
      Hint 
     Hint 
    
    
    
    
     
Please use function scanf

Author

Gardon

Source

Gardon-DYGG Contest 2

문제 풀이 방향:
두 가지 사탕 을 고려 하여 그 중의 가장 큰 수량 이 n 이 라 고 가정 하고 이 두 가지 사탕 을 교체 해서 먹 으 려 면 다른 사탕 의 가장 적은 수량 은 n-1 이다.n 개의 사탕 이 한 줄 로 배열 되 어 있 기 때문에 내부 에 모두 n-1 개의 빈 것 이 있 고 인접 한 두 개의 똑 같은 사탕 을 분리 한다.제목 으로 돌아 가 어떤 사탕 의 최대 수량 인 maxvalue 를 찾 으 려 면 적어도 maxvalue-1 개의 사탕(즉,최대 수량 을 제외 한 사탕)이 공간 을 채 워 야 한다.남 은 사탕 수가 maxvalue 보다 많 으 면 가능 하 다.왜냐하면 우 리 는 수량 이 비교적 적은 사탕 을 원래 의 공간 을 두 껍 게 하 는 데 사용 할 수 있다 고 생각 할 수 있 기 때문이다.즉,두 개 또는 두 개 이상 의 서로 다른 사탕 으로 같은 공간 을 채 울 수 있 기 때문이다.
코드:

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int num[1000002];
int main()
{
    int t;cin>>t;
    int n;
    while(t--)
    {
        int maxvalue=0;
        long long sum=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            maxvalue=max(maxvalue,num[i]);
            sum+=num[i];
        }
        if(sum-maxvalue>=maxvalue-1)//sum-maxvalue        ，maxvalue-1                 
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[ACM]hdu 1205 사탕 먹 기(비둘기 둥지 원리)

HOHO,드디어 Speakless 의 손 에서 모든 사탕 을 이 겼 습 니 다.Gardon 이 사탕 을 먹 을 때 특별한 취미 가 있 습 니 다.바로 똑 같은 사탕 을 같이 먹 는 것 을 좋아 하지 않 습 니 다.먼...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[ACM]hdu 1205 사탕 먹 기(비둘기 둥지 원리)

좋은 웹페이지 즐겨찾기