P7605 20pts 题解

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

思路（显然是假的）

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

我们发现，由于每一次提取的都是最左边或者最右边，所以中间的球不可能比左边和右边的球更早拿出，所以任意时刻，管道中的球都是在原先序列中连续的一段。我们用

[l,r]

表示，初始显然

l=1,r=n

。然后，可以使用语句 while(l<=r){...} 来进行贪心拿球。

然后进行贪心分讨：

$l=r$ ，则无脑直接取出。然后 l++; 之后直接退出循环。
如果 $l\not=r$ $l \neq = 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;。

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

代码

CPP

#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;
}

文章操作

思路（显然是假的）

代码

相关推荐

评论

P7605 20pts 题解