P3619 魔法

考虑两个任务 \(1\) 和 \(2\)，当前时间为 \(T\)，两个任务都要完成。

先完成任务 \(1\) 的条件是 \(T>t_1\) 且 \(T+b_1>t_2\)，先完成任务 \(2\) 的条件是 \(T>t_2\) 且 \(T+b_2>t_1\)。

移项，\(T>t_2-b_1\) 和 \(T>t_1-b_2\)。

假设先完成任务 \(1\) 的条件更松。

那么有 \(t_2-b_1<t_1-b_2\)，即 \(t_1+b_1>t_2+b_2\)。

我们观察到这个东西显然满足传递性和严格弱序，所以按这个比较函数排序即可。

时间复杂度 \(O\left(Zn\log n\right)\)。

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define For(i,x,y)for(i=x;i<=(y);i++)

struct task

{

	int t,b;

}a[100005];

int read()

{

	int A;

	bool K;

	char C;

	C=A=K=0;

	while(C<'0'||C>'9')K|=C=='-',C=getchar();

	while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();

	return(K?-A:A);

}

inline bool cmp(task _,task __)

{

	return _.t+_.b>__.t+__.b;

}

int main()

{

	ll t;

	int z,n,i;

	z=read();

	while(z--)

	{

		n=read(),t=read();

		For(i,1,n)a[i].t=read(),a[i].b=read();

		sort(a+1,a+n+1,cmp);

		For(i,1,n)

		{

			if(a[i].t>=t)break;

			else t+=a[i].b;

			if(t<=0)break;

		}

		puts((i>n?"+1s":"-1s"));

	}

	return 0;

}

巴特西

P3619 魔法

最新文章

热门文章