题解：P14078 [GESP202509 七级] 金币收集

题外话

我用伪

O(n^2)

的做法在 GESP 考场上喜提 22.5 分，但在洛谷上提交居然得了满分。居然这道题是一道绿题，有点惊讶。毕竟我的做法是贪心，感觉最多只值黄题难度。差点就场切绿题了。

思路

我们需要刚好在第

t_i

秒如果在

x_i

的坐标就可以吃到这个金币，首先因为我们只能从左往右走，所以我们会想到按照

x_i

坐标来进行排序，此时我们走到那儿时如果之前从没有原地不动会发现我们还需要等待

t_i-x_i

时间吃到该金币，所以在我们等到那个时间时我们会浪费掉

t_i-x_i

的时间，所以有些金币在等待后是吃不到了。那我们需要预处理每个金币在等待多久之后吃不到了，很简单，那就是拿一个数组

p

存储

t_i-x_i

即可。我们想吃到更多的金币那就找

p

的最长上升子序列，因为我从前往后每个金币都保证一个金币浪费的时间永远会影响到后面的金币。

小提示：

当 $x_i$ 相同时需要按照 $t_i$ 从小往大排序。不然 $x_i$ 相同时前面的 $p_i$ 会影响到后面的 $p_j$ 。
注意 $t_i < x_i$ 的情况。
最长上升子序列需要用二分优化到可以实现 $n \le 10^5$ 做法。

code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct pp{
	int a,b;
}a[230000];
int p[230000],f[230000];
int cmp(pp ap,pp bp){
	if(ap.a==bp.a){
		return ap.b<bp.b;
	}
	return ap.a<bp.a;
}//排序
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].a>>a[i].b;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(a[i].a>a[i].b){
			p[i]=1e12;
		}//注意时间小于坐标
		else{
			p[i]=a[i].b-a[i].a;
		}
	}
    //最长上升子序列
	f[1]=p[1];
	int q=1;
	if(p[1]==1e12){
		f[1]=0;
		q=0;
	}
	for(int i=2;i<=n;i++){
		if(p[i]==1e12){
			continue;
		}
		int l=1,r=q,ans=-1;
		while(l<=r){
			int mid=(l+r)/2;
			if(f[mid]>p[i]){
				r=mid-1;
				ans=mid;
			}
			else{
				l=mid+1;
			}
		}
		if(ans==-1){
			q++;
			f[q]=p[i];
		}
		else{
			f[ans]=p[i];
		}
	}
	cout<<q;
	return 0;
}

题解：P14078 [GESP202509 七级] 金币收集

文章操作

题解：P14078 [GESP202509 七级] 金币收集

题外话

思路

code

相关推荐

评论

题解：P14078 [GESP202509 七级] 金币收集