记录编号	320075	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Nescafé 26] 小猫爬山	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	14.203 s
提交时间	2016-10-11 16:28:57	内存使用	0.30 MiB

#include <ctime>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
typedef double DB;
const int MAXN=1024;
DB MAX_Tempteature=16000000.0;
DB Uper_Temp=4.0;
DB Random_Lost=1000.0;
DB Random_Save=0.0375;
bool vis[MAXN];
int w[MAXN],ansp[MAXN];
int N,UP_LOAD,now_ans=0;
int randomt(){
	return rand()%N+1;
}
double randomt(double x){
	return 1.0*randomt()/N;
}
int Temp_check(){
	int cnt=0,wei=0;
	int temp_ans=1;
	for(int i=1;i<=N;++i){
		if(wei+w[i]>UP_LOAD){
			wei=w[i];
			++temp_ans;
		}else wei+=w[i];
	}if(temp_ans<now_ans){
		now_ans=temp_ans;
		for(int i=1;i<=N;++i)
			ansp[i]=w[i];
		return true;
	}return -true;
}
int Greed_Algorithm(){
	int Greed_ans=0,cnt=0;
	std::sort(w+1,w+N+1);
	for(int i=N;i>=1;--i){
		if(vis[i])continue;
		int now=UP_LOAD-w[i];
		Greed_ans++;
		ansp[++cnt]=w[i];
		for(int j=i-1;now&&j;--j){
			if(w[j]<=now&&!vis[j]){
				ansp[++cnt]=w[j];
				now-=w[j];
				vis[j]=true;
			}
		}
	}now_ans=Greed_ans;
	for(int i=1;i<=N;++i)
		w[i]=ansp[i];
//		printf("hasd");
	return cnt;
}
int Analog_Decrase_Tempteature(){
	Greed_Algorithm();
	int x,y;
	while(MAX_Tempteature>0){
		x=randomt();y=randomt();
		//printf("%d %d\n",x,y);
		if(x==y)continue;
		std::swap(w[x],w[y]);
		if(Temp_check()<0){
			if(Random_Save<randomt(0.0))
				std::swap(w[x],w[y]);
			else MAX_Tempteature+=Uper_Temp;
		}MAX_Tempteature-=2.0;
		Random_Save-=0.0005;
	}return now_ans;
}
int main(){
	freopen("koneko.in","r",stdin);
	freopen("koneko.out","w",stdout);
	srand(time(NULL));
	scanf("%d%d",&N,&UP_LOAD);
	for(int i=1;i<=N;++i){
		scanf("%d",&w[i]);
	}printf("%d",Analog_Decrase_Tempteature());
	//while(true);
	return 0;
}