CF 1262C. Monsters And Spells（区间合并）

53 阅读 0 评论 35 点赞

我是靠谱客的博主辛勤金针菇，最近开发中收集的这篇文章主要介绍CF 1262C. Monsters And Spells（区间合并），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Linking

题意：

有 n 个怪兽，每只怪兽在第 $k_i$ 个时间点出现，每个怪兽有血量 $h_i$ 。
$k_1<k_2<⋯<k_n (1≤k_i≤10^9)，h_1,h_2,…,h_n (1≤h_i≤k_i≤10^9)$
对于一个时间点，如果前一个时间点没有释放攻击的话，攻击力为1；如果前一个时间点释放攻击力为 x，那么当前时间点可以释放攻击力为 x+1 或 1。
要在每个怪兽出现的时间点释放不少于其血量的攻击才能将其消灭。没有怪兽出没的时间点也可以释放攻击。
问将所有怪兽消灭，释放的攻击力之和最少为多少？

思路：

为了当前怪兽出没时能够释放的攻击力不少于其血量，需要前面的时间也释放攻击。
那么对于消灭每只怪兽都需要一段区间来蓄力。
如果两个区间之间有重合的时间，那么肯定有一个区间是要让开的，那么那只怪兽就不能消灭了。
所以如果有重合的话，需要将两个区间合并，用大于血量的攻击来消灭后面那只怪兽。
为了释放的攻击力之和最小，就是还要尽量少合并区间。所以只需要合并有重合有矛盾的区间。

那么这道题目就转化为了 区间合并问题 。
将所有的区间存储下来按照左端点从小到大排序，这样就只需要看相邻的两个区间是不是有重合。
如果两个区间有重合，为了方便操作，我们将后面位置（区间）的 pre 数组存储合并区间的第一个区间的位置，用第一个位置（区间）的 last 数组存储这个合并之后大区间的右端点（左端点肯定是当前区间的左端点了）。

如何知道两个区间是否需要合并呢？
由于区间是按照左端点从小到大排序的，那么如果当前区间的左端点和之前合并的大区间右端点有重合，就说明当前区间和前面区间的右端点有重合，需要合并到大区间中。
而如果当前位置需要合并，由于排序，前一个位置也一定要合并。所以只需要判断当前区间是否和上一区间所属于的大区间有交集。

最后只需要看 pre[i]=i 的位置，即当前区间是合并大区间的首个位置的 last 数组，便可以得到大区间的大小，等差求和计算需要的攻击力。

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m, k; 
PII a[N];
int b[N], pre[N], last[N];

signed main(){
	Ios;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++) cin>>b[i];
		
		for(int i=1;i<=n;i++){
			int x;cin>>x;
			a[i] = {b[i]-x+1, b[i]};
		}
		
		sort(a+1, a+n+1);
		
		for(int i=1;i<=n;i++) pre[i]=i, last[i]=a[i].se;
		
		for(int i=1;i<=n;i++)
		{
			if(a[i].fi<=last[pre[i-1]])
			{
				int x = pre[i-1];
				pre[i] = x;
				last[x] = max(last[x], a[i].se);
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			if(pre[i]==i)
			{
				int m = last[i]-a[i].fi+1;
				ans += m*(1+m)/2;
			}
		}
		cout<<ans<<endl;
	}
	
	return 0;
}