1354. 多次求和构造目标数组


图片说明


堆，数学。

inline int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
class Solution {
public:
typedef long long ll;
    bool isPossible(vector<int>& a) {
        int n=a.size();
        priority_queue<int>q;
        ll sum=0;
        int g=0;
        for(int i=0;i<n;i++){
            q.push(a[i]),sum+=a[i];
            g=gcd(g,a[i]);
        }
        if(sum==n)return 1;
        if(g!=1)return 0;
        while(true){
            int tp=q.top();
            q.pop();
            if(tp==1&&sum==n)return 1;
            sum-=tp;
            if(tp<sum)return 0;
            int x=tp%sum;
            if(sum==1)x=1;
            if(x==0&&sum!=1)return 0;
            q.push(x);
            sum+=x;
        }
        return 1;
    }
};