题目描述
达达现在碰到了一个棘手的问题,有N个整数需要排序。
达达手头能用的工具就是若干个双端队列。
她需要依次处理这N个数,对于每个数,达达能做以下两件事:
1.新建一个双端队列,并将当前数作为这个队列中的唯一的数;
2.将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后,达达将这些队列排序后就可以得到一个非降的序列。
请你求出最少需要多少个双端序列。
输入格式
第一行输入整数N,代表整数的个数。
接下来N行,每行包括一个整数Di,代表所需处理的整数。
输出格式
输出一个整数,代表最少需要的双端队列数。
数据范围
1≤N≤200000
样例
输入样例:
6
3
6
0
9
6
3
输出样例:
2
模拟+贪心
这道题目真的和双端队列没有什么关系.这道题目的解题思路大致如下:首先我们可以敏锐地找出两个性质.
- 双端队列内部的所有数,一定满足单调性,也就是排好序了
- 所有的双端队列排在一起,肯定是满足单调性,也就是也都排好序了
接着来思考,我们发现正面思考非常地难,所以我们反向思考问题,把一个A[1,n]的已经拍好顺序的序列,分成尽量少的段,然后每一段都是一个双端队列.
然后我们不妨,开一个数组也就是B数组,记录原数组A的每一个数的下标,然后我们发现如果B的一段满足单峰性质,也就是书上更为确切的单谷性质,那么这一段就满足条件.因为单谷性质,前半段可以视为从队头加入,后半段视为从队尾加入.单谷性质具体可以百度.
特殊情况是,如果有重复的点,也就是值相同的几个点.这个特别难以理解,个人觉得.
比较容易地理解就是,将这个值一样的点,缩点.缩成一个点就好了,反正我们只要队列的个数,不要方案,而且只要满足单调性就好,记住不是严格单调性.
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=200100;
#define pii pair<int,int>
#define fir(i,a,b) for(int i=a;i<=b;i++)
pii a[N<<1];
int cmp(pii a,pii b)
{
return a.first==b.first ? a.second<b.second : a.first>b.first;;
}
int n,h,b,mx[N],mi[N],cnt,ans;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
fir(i,1,n)
cin>>a[i].first,a[i].second=i;//first为值,second为下标
sort(a+1,a+1+n,cmp);
fir(i,1,n)
if (a[i].first!=a[i-1].first || i==1)//缩点
{
mx[cnt]=a[i-1].second;
mi[++cnt]=a[i].second;
}
mx[cnt]=a[n].second;
b=true;
h=1<<30;
fir(i,1,cnt)
if (!b)
{
if (h>mx[i])
h=mi[i];
else
h=mx[i],b=true;//单调性开始变化
}
else
{
if (h<mi[i])
h=mx[i];
else
h=mi[i],b=false,ans++;//单调性开始变化,同时记录值,因为当前已经抵达单谷.
}
cout<<ans;
return 0;
}
对于重复的值我是这样处理的,首先同一值位置要么递增放,要么递减放,那么我只要存最大最小值,然后dp去求解“谷” 最少得方案。// dp[i][0/1] 第 i 小的值 (递增/递减) 时,谷最少是多少,最后一段递减的先不算,在转移和输出答案时算上。这是我的代码:
#include[HTML_REMOVED]
#define int long long
using namespace std;
const int inf = 1e8, N = 2e5 + 10;
int n,m;
map[HTML_REMOVED]> mp;
pair[HTML_REMOVED] p[N];
int dp[N][2];
signed main(){
cin >> n;
for(int i=1;i<=n;i){
int x;
cin >> x;
if(mp.count(x) == 0){
mp[x] = {i,i};
}
else{
mp[x].first = min(mp[x].first,i);
mp[x].second = max(mp[x].second,i);
}
}
m = mp.size(); int idx = 0;
for(auto [x,y] : mp){
p[idx] = y;
}
dp[1][0] = 1;
for(int i=2;i<=m;i++){
dp[i][0] = dp[i-1][0] + (p[i].first < p[i-1].second);
dp[i][0] = min(dp[i][0], dp[i-1][1] + 1);
dp[i][1] = dp[i-1][0];
dp[i][1] = min(dp[i][1],dp[i-1][1] + (p[i].second > p[i-1].first));
}
cout << min(dp[m][0], dp[m][1] + 1);
}
%%%
%%%
%%%蓝书的每一道例题的代码都写得好好!!
大佬有可能一开始递增答案会更佳吗
木有听懂,一开始递增是啥意思?是这道题目吗?
是啊
做的时候假定一开始递减
递减应该好一些,不过您可以改一下,测试一波就知道了.
我认为没有可能;贪心求最少的谷底数,如果一开始递增则初始谷底数就是一,算出的答案要么和正确答案相同(刚开始就是递增),要么比正确答案多一(刚开始是递减)。
请问这个mi数组和mx数组是干嘛用的,不太理解
最小数组和最大数组用来测试单谷函数的