站外模拟退火求助
  • 板块灌水区
  • 楼主Hywel
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/10/12 09:46
  • 上次更新2023/11/4 04:01:05
查看原帖
站外模拟退火求助
90510
Hywel楼主2021/10/12 09:46

某人把每个任务所需的时间和现在(0 时刻)距离每个任务截稿的时间记录了下来, 想要计算出最多可以完成多少任务。

输入描述 第一行是一个整数 N,接下来 N 行每行两个整数 T1,T2 描述一个任务:

完成这个任务需要 T1 秒,如果在 T2 秒之内还没有完 成任务,这个任务就到截稿时间了。

输出描述 输出一个整数 S,表示最多可以完成 S 个任务.

样例输入

4
100 200
200 1300
1000 1250
2000 3200

样例输出

3

数据范围及提示

对于 30%的数据, N≤100;

对于 60%的数据, N≤10000;

对于 80%的数据, N < 150,000; T1 < T2 < INT_MAX;

对于 100%的数据, N < 150,000; T1 < T2 < LLONG_MAX; 所有数据保证随机生成

不求时间复杂度,只求模拟退火解对,请问哪里有问题?

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
template<typename T>inline void read(T &x)
{
	x = 0 ; int w = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch=getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	x *= w;
	FUCKER:;
}
template<typename T>inline void write(T x)
{
	if(x == 0){putchar('0');return ;}
	if(x < 0){putchar('-');x = -x;}
	if(x > 9){write(x / 10);
	}
	putchar(x % 10 + '0');
	FUCKER:;
}
/* ----------------------------------------------------------------------------------------------------------------------*/
const int maxn = 1e6 + 1;
int n ;
struct node
{
	int need;
	int limit;
}a[maxn];
inline ll calc()
{
	ll res = 0 , cnt = 0;
	for(int i = 1 ; i <= n ; i ++)
	{
		res += a[i].need ;
		if(res < a[i].limit) cnt++;	
		else 
		{
			res -= a[i].need ;
			break;
		}
	}
	return cnt;
}
bool cmp(const node &x , const node &y)
{
	if(x.need == y.need)
		return x.limit < y.limit;
	return x.need < y.need;
}
ll ans;
const double delta = 0.999999;
inline void break_fire()
{
	int T = 2000;
	int now_ans = ans;
	while(T > 1e-20)
	{
		int x = rand() % n + 1 , y = rand() % n + 1;
		swap(a[x] , a[y]);
		now_ans = calc();
		int DE = now_ans - ans;
		if(DE > 0)	ans = now_ans;
		else if(exp(-DE / T) * RAND_MAX < rand())
			swap(a[x] , a[y]);
		T *= delta;
	}
}
signed main()
{
	srand(time(0));
	read(n);
	for(int i = 1 ; i <= n ; i ++)
		read(a[i].need) , read(a[i].limit);
	sort(a + 1 , a + n + 1 , cmp);
	ans = calc();
	while((double)clock()/ CLOCKS_PER_SEC < 0.9)break_fire() ; 
	write(ans);
	FUCKER:;
	return 0;
}

2021/10/12 09:46
加载中...