Wannafly 챌 린 지 29 A

2096 단어 알고리즘
링크:https://ac.nowcoder.com/acm/contest/271/A 우 객 망 
제목 설명
미 사 카 는 개굴개굴 태 할아버지 의 작은 팬 이다. 개굴개굴 태 할 아버 지 는 '한 척 의 몽둥이 로 하루 에 반 을 취하 면 영원히 다 하지 않 는 다' 는 말 이 있다.misaka 는 현재 n 개의 개굴개굴 인형 을 한 더미 에 놓 고 있 습 니 다. 매번 조작 할 때마다 misaka 는 현재 개수 > 1 의 개굴개굴 인형 을 선택 합 니 다.그리고 이 개굴개굴 인형 더 미 를 두 더미 로 나 누 었 습 니 다. x 는 현재 이 인형 더미 의 개수 입 니 다.현재 misaka 는 인형 을 m 더미 로 나 누고 싶 습 니 다. 그 중에서 i 더미 의 개 수 는 ai 입 니 다. misaka 가 몇 번 의 조작 을 통 해 인형 을 지정 한 m 더미 로 나 눌 수 있 는 지 알려 주 셔 야 합 니 다.출력 할 수 있다 면, 그렇지 않 으 면 출력 합 니 다.
입력 설명:
       n, m 。
      m    ai 。

출력 설명:
         ，   misaka            m  。

예시 1
입력
4 1
5

출력
ham

비고:
1 ≤ n ≤ 1018, 1 ≤ m ≤ 105, 1 ≤ ai ≤ 1018。
      ，   misaka            m  。

생각:
이 문 제 는 처음에 우선 대기 열 로 m 개 수 를 유지 하 는 것 이 었 습 니 다. n 을 모 을 수 있 는 지 없 는 지 를 보 았 습 니 다. 다른 생각 은 n 을 분해 하 는 방식 이 유일 하기 때문에 m 개 수 와 다르다 고 판단 하면 됩 니 다. 그러나 가지치기 에 주의해 야 합 니 다. 그렇지 않 으 면 시간 을 초과 할 수 있 습 니 다.
코드:
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long

using namespace std;
const int maxn=1e5+100;
LL a[maxn];
mapmp;
LL cnt=0,m=0,sum=0,n=0;
bool flag=true;
void dfs(LL x)
{
    if(mp.find(x)!=mp.end()&&mp[x]>0)
    {
        cnt++;
        mp[x]--;
        sum+=x;
        return;
    }
    if(x<=1||cnt==m||sum==n)
    {
        flag=false;
        return ;
    }
    LL p1=x/2;
    if(flag)
        dfs(p1);
    LL p2=x-x/2;
    if(flag)
        dfs(p2);
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&a[i]);
        mp[a[i]]++;

    }
    dfs(n);
    if(sum==n&&cnt==m)
    {
        printf("misaka
");
    }
    else
    {
        printf("ham
");
    }
    return 0;
}

css3 애니메이션의 시작 시간과 지속 시간을 어떻게 편리하게 제어합니까
USACO 6.3 가지치기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage