【思维 + 贪心】AcWing 134. 双端队列

这题的思想还是很有意思的~

分析

考虑将读入的数处理成 pair 数组,第一个属性代表读入的值,第二个属性代表下标
然后将 pair 数组对升序排序,可以发现,如果想要 pair 连续的一段出现在同一个双端队列中,那么下标一定是先递减再递增(像山谷一样)(当然,单调这种退化的形式也算)。

为什么下标一定是先递减再递增呢?因为值处于中间的元素下标值一定是最小的,而越向两边扩展,其下标一定越大,因此呈山谷一样的形状。

有了这个性质,下面考虑如何统计答案。

因为相同的值之间对应的下标值可以相互调整,我们需要找到最优的调整方案使得山谷出现次数最小。

  • 直观地考虑,先将值相同的每一段对应的下标值存起来(具体实现可以用 vector)。

  • 接着从左到右扫一遍,维护一个状态 \(ok\),\(ok=1\) 时代表正在递减状态,否则为递增状态。

  • 不难发现初始状态设置为 \(ok=1\) 一定是最优的。

最后分类讨论:

  1. 第 \(i-1\) 段 \(ok=1\) 时,当第 \(i\) 段的最大值比 \(i-1\) 段的最小值小,那么我们这一段也贪心地决策为递减(也就是 \(ok\) 值保持);否则,我们贪心地将 \(ok\) 变为 \(0\)。
  2. 第 \(i-1\) 段 \(ok=0\) 时,当第 \(i\) 段的最小值比 \(i-1\) 段最大值大,那么我们这一段也决策为递增;否则,我们贪心地将 \(ok\) 变为 \(1\)。

为什么这样贪心是对的呢?

以第一个情况为例,第二个类似。

  • 当第 \(i\) 段的最大值比 \(i-1\) 段的最小值小,我们保持第 \(i\) 段 \(ok=1\)(决策保持单减)(我们记为决策 \(1\)),我们证明这样做一定不比决策变为单增(记为决策 \(2\))

证明:
第 \(i+1\) 段如果我们决策为 \(ok=1\),那么决策 \(1\) 的 \(i-1,i,i+1\) 三段的总代价为 \(\leq 2\),而决策 \(2\) 的代价为 \(2\)。
第 \(i+1\) 段如果我们决策为 \(ok=0\),那么决策 \(1\) 的 \(i-1,i,i+1\) 三段的总代价为 \(1\),而决策 \(2\) 的代价为 \(\geq 1\)。
因此无论 \(i+1\) 段如何决策,决策 \(1\) 都不比 \(2\) 差。

  • 当第 \(i\) 段的最大值比 \(i-1\) 段的最小值大,我们让第 \(i\) 段 \(ok=0\)(决策改变为单增)(我们记为决策 \(1\)),我们证明这样做一定不比决策第 \(i\) 段 \(ok=1\)(保持单减,记为决策 \(2\))

证明:
第 \(i+1\) 段如果我们决策为 \(ok=1\),那么决策 \(1\) 的 \(i-1,i,i+1\) 三段的总代价为 \(2\),而决策 \(2\) 的代价为 \(\geq 2\)。
第 \(i+1\) 段如果我们决策为 \(ok=0\),那么决策 \(1\) 的 \(i-1,i,i+1\) 三段的总代价为 \(\leq 2\),而决策 \(2\) 的代价为 \(2\)。
因此无论 \(i+1\) 段如何决策,决策 \(1\) 都不比 \(2\) 差。

至此,证明完毕。

实现

// Problem: 双端队列
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/136/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()

using pii = pair<int, int>;
using ll = long long;

inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

#define x first
#define y second

const int N=2e5+5;

int n;
pii e[N];

int main(){
	cin>>n;
	rep(i,1,n) read(e[i].x), e[i].y=i;
	sort(e+1, e+1+n);
	
	vector<vector<int>> blk;
	
	vector<int> rec;
	rec.pb(e[1].y);
	rep(i,2,n){
		if(e[i].x!=e[i-1].x){
			blk.pb(rec);
			rec.clear();
		}
		rec.pb(e[i].y);
	}
	if(rec.size()) blk.pb(rec);

	if(blk.size()==1) return puts("1"), 0;
	bool ok=1;
	int res=1;
	rep(i,1,blk.size()-1){
		if(ok){
			if(*min_element(all(blk[i-1]))<*max_element(all(blk[i]))){
				ok=0;
			}
		}
		else{
			if(*max_element(all(blk[i-1]))>*min_element(all(blk[i]))){
				ok=1;
				res++;
			}
		}
	}
	
	cout<<res<<endl;
	
	return 0;
}
上一篇:1017 Queueing at Bank (25 分)


下一篇:PAT甲级 1017 Queueing at Bank