概念
使用两个指针维护一段序列区间，保证左指针一定小于右指针，并且指针只会向右移动。
右指针每次向右移动一格；对于右指针的每一个位置，左指针也向右移动，直到所代表的区间满足条件为止。
例题
洛谷P1638 逛画展
题意
博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。
游客在购买门票时必须说明两个数字，$a$ 和 $b$，代表他要看展览中的第 $a$ 幅至第 $b$ 幅画（包含 $a,b$）之间的所有图画，而门票的价钱就是一张图画一元。
Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。
请求出他购买门票时应选择的 $a,b$，数据保证一定有解。
若存在多组解，输出 $a$ 最小的那组。
$1\leq n\le10^6$，$1 \leq a_i \leq m\le2\times10^3$。
解析
题目需要求区间的两个端点，则可用左右指针分别代表区间的两个端点。
每次左指针向右移动，直至区间里的数有 $m$ 种为止。
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define inf 2147483647
int n,m,ans=inf,sum,ansl,ansr;
int a[N],f[N];
void add(int x){
f[a[x]]++;
if(f[a[x]]==1) sum++;
}
void mns(int x){
f[a[x]]--;
if(f[a[x]]==0) sum--;
}
int main(){
int i;
cin>>n>>m;
for(i=1;i<=n;i++) cin>>a[i];
int l=0,r=1;
for(r=1;r<=n;r++){
add(r);
while(sum==m&&l<=r){
mns(++l);
if(ans>r-l) ans=min(ans,r-l),ansl=l,ansr=r;
}
}
cout<<ansl<<' '<<ansr<<endl;
return 0;
}
|
洛谷P4653 [CEOI2017] Sure Bet
题意
现在有 $n$ 个 $A$ 类灯泡和 $n$ 个 $B$ 类灯泡，每个灯泡都有各自的权值。
我们将这些灯泡分为 $n$ 组，每组包含一个来自A类的灯泡和一个来自B类的灯泡。
你可以从中选取任意个灯泡，每选取一个灯泡需要花费 $1$ 的代价。
在你选取完之后，系统会随机在A类和B类中选择一个类型，并点亮那一类的所有灯泡。你选取的每个点亮的灯泡会给你带来等于它权值的收益。
现在请你合理选取灯泡，以最大化可能的最小收益。你只需要求出来这个收益即可。
$1.0\le A_i,B_i\le 1000.0$，$0\le n\le 10^5$。
解析
当选取的 $A$ 组物品总价值大于 $B$ 组时，只有从 $B$ 组选取才能达到更优解
从另一组选取时，需要使两组物品的价值尽可能相等
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void qmax(T &x,const T &y){if(x<y) x=y;}
#define N 100005
int n;
double a[N],b[N],ans1,ans2,ans;
bool cmp(double a,double b){return a>b;}
int main(){
int i,l=0,r;
cin>>n;
for(i=1;i<=n;i++) scanf("%lf%lf",&a[i],&b[i]);
sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp);
for(r=1;r<=n;r++){
ans1+=a[r];
qmax(ans,min(ans1-(l+r),ans2-(l+r)));
while(ans2<=ans1&&l<=n) ans2+=b[++l],qmax(ans,min(ans1-(l+r),ans2-(l+r)));
}
printf("%.4lf",ans);
return 0;
}
|
