淘淘与蓝蓝之电电⿏⼤战御坂美琴

题目大意

给出 (n，W，ct) 表示有 (ct) 个 (n) 的约数，每个大小为 (d_i) 且有 (a_i) 个相同的
现将其放入 (W) 大的空间中，问最多能装满多少空间
对于 (100%) 的数据，(1leq nleq 10^4，1leq a_i,Wleq 10^{15})

分析

显然想到背包
然后发现 (W) 太可怕，果断舍弃
其实，可以考虑随机化贪心
我们让这几个数排成一个序列，从头到尾能取多少就取多少
然后做很多次
与我们我们能拿到 (85) 分的好成绩（数据太废）
或者同理模拟退火，同样可以拿到 (85) 分的好成绩（数据太废）

于是剩下 (15) 分怎么搞都搞不到
但我们不能放弃
于是在隔壁大神 (LZC) 的指导下
我们可以将两者结合起来
首先随机化贪心，同上，并记录每个数选了多少个
然后模拟退火
随机 (x，y，z)
表示第 (x) 个数少取 (z) 个，剩余空间给第 (y) 个数尽量多取
于是非常高兴地 (A) 了

(Code)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#define LL long long 
using namespace std;

const int N = 64;
int n , ct;
LL W , ans = 0 , cur; 
struct node{
	int d; LL a , c;
}s[N] , tmp[N];

LL getans()
{
	LL w = W;
	for(register int i = 1; i <= ct; i++)
	{
		if (w <= 0) break;
		s[i].c = min(s[i].a , w / s[i].d);
		w -= s[i].c * s[i].d;
	}
	return W - w;
}
void RG()
{
	for(register int i = 1; i <= ct; i++) tmp[i] = s[i];
	random_shuffle(s + 1 , s + ct + 1);
	LL c = getans();
	if (c > ans) ans = cur = c;
	else for(register int i = 1; i <= ct; i++) s[i] = tmp[i];
}
void SA()
{
	srand(time(NULL));
	double T = 5000 , delta = 0.998;
	LL x , y , z , v , cx , cy;
	while (T > 1e-14)
	{
		x = (LL)(rand() * T) % ct + 1;
		y = (LL)(rand() * T) % ct + 1;
		z = (LL)(rand() * T) % (s[x].c + 1);
		cx = s[x].c , cy = s[y].c , v = cur;
		s[x].c -= z , v -= z * s[x].d;
		z = min(s[y].a - s[y].c , (W - v) / s[y].d);
		s[y].c += z , v += z * s[y].d;
		if (v > ans) ans = cur = v;
		else if (exp((v - ans) / T) * RAND_MAX > rand()) cur = v;
		else s[x].c = cx , s[y].c = cy;
		T *= delta;
	}
}

int main()
{
	freopen("dedenneVSbilibili.in" , "r" , stdin);
	freopen("dedenneVSbilibili.out" , "w" , stdout);
	scanf("%d%lld%d" , &n , &W , &ct);
	for(register int i = 1; i <= ct; i++) scanf("%d" , &s[i].d);
	for(register int i = 1; i <= ct; i++) scanf("%lld" , &s[i].a);
	for(register int i = 0; i < 10; i++) RG();
	for(register int i = 0; i < 10; i++) SA();
	printf("%lld
" , ans);
}