某人把每个任务所需的时间和现在(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;
}