模拟退火

class Solution {
public:
    int n, m, res;
    vector<int> w;

    int calc(){
        int cnt = 1;
        for(int i = 0, s = 0; i < n; i ++ ){
            s = (s + w[i]) % m;
            if(!s && i < n - 1)cnt ++;
        }
        res = max(res, cnt);
        return cnt;
    }

    void simulate_anneal(){
        random_shuffle(w.begin(), w.end());

        for(double t = 1e6; t > 1e-5; t *= 0.97){
            int a = rand() % n, b = rand() % n;
            int x = calc(); //计算交换前结果
            swap(w[a], w[b]);
            int y = calc(); //计算交换后结果
            int delta = y - x; //这次交换的评价值：> 0，说明变好，不会进入下面的if， < 0 说明变差，以一定概率交换
            if(exp(delta / t) < (double)rand() / RAND_MAX){
                swap(w[a], w[b]);
            }
        }
    }
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        n = groups.size(), m = batchSize;
        w = groups, res = 0;
        for(int i = 0; i < 80; i ++ )simulate_anneal();
        return res;
    }
};