题解：CF2126D This Is the Last Time

\color{blue}{\texttt{[Translation]}}

你有一个初始硬币价值

k

和

n

个操作，每个操作形如

[l_{i},r_{i},\text{real}_{i}]

。对于每个操作，如果你当前的硬币价值满足

l_{i} \leq \text{cur} \leq r_{i}

，则你的硬币价值变成

\text{real}_{i}

。你可以按任意次序进行任意次操作，求最终最大的可能的硬币价值。

1 \leq n \leq 1 \times 10^{5},l_{i} \leq \text{real}_{i} \leq r_{i}

。

Translated by HPXXZYY.

\color{blue}{\texttt{[Analysis]}}

贪心。

显然，

r_{i}

对于我们是没有用的，因为当

\text{cur}>\text{real}_{i}

时就算满足条件你也不会进行操作；当

\text{cur}<\text{real}_{i}

时，

\text{cur}

当然也小于

r_{i}

。所以，我们将操作化简为

[l_{i},R_{i}]

，其中

R_{i}=\text{real}_{i}

，当

l_{i}\leq \text{cur} \leq R_{i}

时，可以将

\text{cur}

变成

R_{i}

。

按操作的

l

从小到大进行排序，如果

\text{cur} \geq l_{i}

，就贪心的进行操作，最终答案一定最优。

为什么这样贪心是正确的呢？是否有这样的可能，我们需要先进行某次操作 $v$ 使得 $\text{cur}$ 变小，进入另一个操作 $u$ 的区间，再通过操作 $u$ 使得 $\text{cur}$ 变大？

其实是有这样的可能的，但是这道题不会。核心的原因在于 $\text{real}_{i}\leq r_{i}$ 。

最开始 $\text{cur}$ 不在 $u$ 的操作区间的原因是 $\text{cur}>r_{u}$ ，即使我们最终通过一系列花里胡哨的操作使得 $\text{cur}^{'}$ 进入了 $u$ 的可操作区间 $[l_{u},r_{u}]$ ， $\text{cur}>r_{u}\geq \text{real}_{u}$ ，最终变劣了。

\color{blue}{\text{Code}}

CPP

int T,n,k,l[N],r[N],order[N];
 
bool cmp(int u,int v){
	if (l[u]==l[v])
		return r[u]>r[v];
	return l[u]<l[v];
}
 
int main(){
	T=read();
	while (T--){
		n=read();k=read();
		for(int i=1;i<=n;i++){
			l[i]=read();
			read();
			r[i]=read();
			order[i]=i;
		}
		
		sort(order+1,order+n+1,cmp);
		
		for(int i=1;i<=n;i++)
			if (l[order[i]]<=k&&k<=r[order[i]])
				k=r[order[i]];
		
		printf("%d\n",k);
	}
	
	return 0;
}

题解：CF2126D This Is the Last Time

文章操作

相关推荐

评论

题解：CF2126D This Is the Last Time