Leetcode 1815. 得到新鲜甜甜圈的最多组数(模拟退火）

代码语言：javascript复制

class Solution {
public:
    vector<int>w;
    int ans=-1,b;
    int calc(){
        int res=1,s=0;
        for(int i=0;i<w.size();i  ){
            s=(s w[i])%b;
            if(!s&&i<w.size()-1)res  ;
        }
        ans=max(ans,res);
        return res;
    }
    void simulate_anneal(){
        int n=w.size();
        random_shuffle(w.begin(),w.end());
        for(double t=1e6;t>1e-6;t*=0.97){
            int a=rand()%n,b=rand()%n;
            int x=calc();
            swap(w[a],w[b]);
            int y=calc();
            int delta=x-y;
            if(!(exp(-delta/t)> (double)rand() / RAND_MAX) ){
                swap(w[a],w[b]);
            }
        }   
    }
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        w=groups,b=batchSize;
        for(int i=0;i<70;i  )simulate_anneal();
        return ans;
    }
};

leetcode

0 人点赞