链接

点击跳转

题解

这个题是个思维题

首先如果所要求的数字之和不等于n，就直接判为无解。这一点很重要，可以保证后面算法的复杂度。

然后不停的把最大的分成两半，随时把符合条件的堆删掉，如果要求的堆的最大值多于当前分出来的堆的最大值，那么就直接判为无解。如果最后是有解的话，事情就会很顺利，做这个事情的过程有点像一层一层遍历线段树，但是因为我用堆维护，所以复杂度是mlogm。如果最后无解的话，由于我最开始判了和相等，所以可以保证非常早的退出，试想最大值最小情况下是 n m \frac{n}{m} mn​也就是 1 0 13 10^{13} 1013级别，也不会出现超时的问题。那么那我大概要往下分个17层左右，也就是说最后堆里面元素的个数也就是大概 2 m 2m 2m个数这么多，还是不会超时。

代码

#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>#define iinf 0x3f3f3f3f#define linf (1ll<<60)#define eps 1e-8#define maxn 1000010#define maxe 1000010#define cl(x) memset(x,0,sizeof(x))#define rep(i,a,b) for(i=a;i<=b;i++)#define drep(i,a,b) for(i=a;i>=b;i--)#define em(x) emplace(x)#define emb(x) emplace_back(x)#define emf(x) emplace_front(x)#define fi first#define se second#define de(x) cerr<<#x<<" = "<<x<<endlusing namespace std;using namespace __gnu_pbds;typedef long long ll;typedef pair<int,int> pii;typedef pair<ll,ll> pll;ll read(ll x=0){ll c, f(1);for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;for(;isdigit(c);c=getchar())x=x*10+c-0x30;return f*x;}int main(){ll n=read(), m=read(), i, S=0;multiset<ll> s;priority_queue<ll> heap;heap.push(n);rep(i,1,m){ll x=read();s.insert(x);S+=x;}if(S!=n){printf("ham");return 0;}while(!heap.empty()){while(s.find(heap.top())!=s.end()){auto x = heap.top(); heap.pop();auto it = s.find(x);s.erase(it);}if(!heap.empty() and !s.empty() and heap.top()<*s.rbegin()){printf("ham");return 0;}if(heap.empty())break;auto x=heap.top(); heap.pop();if(x/2)heap.push(x/2);heap.push(x-x/2);}if(s.empty())printf("misaka");else printf("ham");return 0;}