P7605 20pts 题解

Cute_OIer · 2025-10-19 08:50:33 · 个人记录

p.s. 现在这道题只有 UnAccepted 和 Accepted 了。

思路（显然是假的）

发现数据范围较小，所以显然可以直接模拟。考虑贪心。

我们发现，由于每一次提取的都是最左边或者最右边，所以中间的球不可能比左边和右边的球更早拿出，所以任意时刻，管道中的球都是在原先序列中连续的一段。我们用 [l,r] 表示，初始显然 l=1,r=n。然后，可以使用语句 while(l<=r){...} 来进行贪心拿球。

然后进行贪心分讨：

• 如果 l\not=r，那么我们需要进行稍复杂的分类：
  • 首先，我们发现，我们需要将杯子的大小优化到最小，所以可以找找距离 a_l 最近的一个颜色相同的球，也找出距离 a_r 最近的一个颜色相同的球。我们用函数 p(x,c) 表示最近的一个的序号，其中 x 表示颜色，c（char）表示左边还是右边。如果 p(x,c)=-1 则代表找不到。这里使用 pl=p(a[l],'l') 以及 pr=p(a[r],'r') 即可。
  • 如果 pl=pr=-1，那么就是原先的队列里面都没有了，我们考虑左右两端的球有无在杯子最上面的（注意，这里杯子相当于栈）。如果有，那么就先塞那个，否则先塞 a_l 再塞 a_r。为什么不把杯子全部遍历一遍？因为就算里面有也取不出来了。然后 l++,r--;，并且更新杯子的大小和最大大小。
  • 如果 pl=-1,pr\not=-1，则优先放入 a_r（贪心做法），反之亦然。不过依然要更新 l 或者 r，以及杯子大小和最大大小。
  • 如果 pl\not=-1,pr\not=-1，那么还是一个贪心，如果有至少一个能够塞进去之后就消掉，那就放那个。如果都消不掉，那么找 \operatorname{dist}(l,pl) 和 \operatorname{dist}(r,pr) 中较小的一个，因为它这样可能消掉的概率较大。纯猜。 然后进行更新。
• 最后，输出最大大小和最终杯子里面球的个数即可。

但是，还有一个问题，就是怎么把球塞进去，然后模拟消除的问题？我们进行判断，如果塞进去的和栈顶相等，那么 top--;，否则 st[++top]=x;。

不过还有一个坑点：就算是能够消除，那么这个栈（杯子）的最大大小还是要按照没有消除的算的。这就很坑了。

代码

#include<bits/stdc++.h>
#define int long long
#define INF 1145141919810
using namespace std;
int n,a[1201],l,r;
int top,st[1201]={INF},mx;
int p(int x,char op){
    if(op=='l'){
        for(int i=l;i<=r;i++)
            if(a[i]==x)
                return i;
    }
    else{
        for(int i=r;i>=l;i--)
            if(a[i]==x)
                return i; 
    }
    return -1;
}
int dist(int x,int y){
    return abs(x-y);
}
void ins(int x){
    if(x==st[top])top--,mx=max(mx,top+2);
    else st[++top]=x;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    l=1,r=n;
    while(l<=r){
        if(l==r){
            ins(a[l]);
            l++;
        }
        else{
            int pl=p(a[l],'l'),pr=p(a[r],'r');
            if(pl==-1&&pr==-1){
                if(st[top]==a[r]){
                    ins(a[r]);ins(a[l]);
                }
                else{
                    ins(a[l]);ins(a[r]);
                }
                l++,r--;
                mx=max(mx,top);
            }
            else if(pl==-1){
                ins(a[r]);
                r--;
                mx=max(mx,top);
            }
            else if(pr==-1){
                ins(a[l]);
                l++;
                mx=max(mx,top);
            }
            else{
                if(st[top]==a[l]){
                    ins(a[l]);
                    l++;
                }
                else if(st[top]==a[r]){
                    ins(a[r]);
                    r--;
                }
                else if(dist(l,pl)>dist(r,pr)){
                    ins(a[r]);
                    r--;
                }
                else{
                    ins(a[l]);
                    l++;
                }
                mx=max(mx,top);
            }
        }
        mx=max(mx,top);
//      cout<<"top="<<top<<"\n";
//      for(int i=1;i<=top;i++)
//          cout<<st[i]<<" ";
//      cout<<"\n";
    }
    cout<<top<<" "<<mx;
    return 0;
}