Greedy and Solve reversely part 2

Some problems when solving reversely, it will be very efficient.

Yesterday’s weekly contest had this kind of problem.

1354. Construct Target Array With Multiple Sums

We can use a map to recording the whole process.

class Solution {
public:
    bool isPossible(vector<int>& target) {
        map<int, int> mp;
        long long sum = 0;
        for(auto&t:target){++mp[t];sum+=t;}
        
        while(!mp.empty()){
            auto it = mp.end();--it;
           long long val = it->first-(sum-it->first);
           sum = sum-it->first+val;
            if(val<1)return false;
            mp[val]++;it->second--;
            if(it->second<=0)mp.erase(it);
            if (mp.size()==1)return mp.begin()->first==1?true:false;
        }
        return false;
        
    }
};

Also, a multiset can be used here to make the code more concise.

class Solution {
public:
    bool isPossible(vector<int>& target) {
        long long sum = 0;
        for(auto&t:target)sum+=t;
        multiset<int> ms(target.begin(), target.end());
        while(!ms.empty()){
            auto it = --ms.end();
            if(*it==1)return true;
           long long val = *it-(sum-*it);
           sum = sum-*it+val;
            if(val<1)return false;
            ms.erase(it);
            ms.insert(val);
        }
        return false;
    }
};