模拟退火的
题目链接
体验乱调参数而看天意的奇特体验
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int inf=0x3f3f3f3f;
const int N=1e5+10;
const int mod=1e9+7;
//#define int long long
const ll INF=2e9+10;mt19937_64 rd(23333);
uniform_real_distribution<double> drd(0.000001,0.99999);int n,m,c,res;
int a[300];
int b[30][30];
int nx[4]={0,1,0,-1},ny[4]={1,0,-1,0};
int ans[30][30],q;void init(){int pos=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){while(a[pos]==0)pos++;a[pos]--;b[i][j]=pos;ans[i][j]=b[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<4;k++){int xx=i+nx[k];int yy=j+ny[k];if(xx<1||xx>n||yy<1||yy>m)continue;if(b[xx][yy]!=b[i][j])res++;}}}res/=2;q=res;
}int cal(int x,int y){int re=0;for(int k=0;k<4;k++){int xx=x+nx[k];int yy=y+ny[k];if(xx<1||xx>n||yy<1||yy>m)continue;if(b[xx][yy]!=b[x][y])re++;}return re;
}void sa(){for(int t=1e15;t>=1e-15;t*=0.9999){int x1=(rd()%n)+1;int y1=(rd()%m)+1;int x2=(rd()%n)+1;int y2=(rd()%m)+1;if(b[x1][y1]==b[x2][y2])continue;int pre=cal(x1,y1)+cal(x2,y2);swap(b[x1][y1],b[x2][y2]);int nex=cal(x1,y1)+cal(x2,y2);int temp=res+nex-pre;int sub=res-temp;if(sub>0){res=temp;if(res<q){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans[i][j]=b[i][j];q=res;}}else if(exp(sub/t)<1.0*drd(rd))res=temp;elseswap(b[x1][y1],b[x2][y2]);}
}void solve(){cin>>n>>m>>c;for(int i=1;i<=c;i++)cin>>a[i];init();while(clock()/(1.0*CLOCKS_PER_SEC)<=4.89) sa();//cout<<q<<endl;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j>1) cout<<' ';cout<<ans[i][j];}cout<<endl;}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;//cin>>t;while(t--){solve();}return 0;
}