2 条题解
-
4
SOLUTION
这貌似是贪心 round ,看起来这个题像是贪心了,于是先想贪心。
首先发现
NOI,IOI都以O作为中心,直觉上认为要枚举O,判断他的两边的情况。能不能从前往后枚举
O,假设前面的O已经处理完了,所以我们从前面随便选一个没用过的I或N当开头。对于后面的,由于选太往前的
I会导致后面没有I当开头,于是直接选最后面没用过的I。这个算法显然是假的,因为他过不了样例 1,具体原因是后面的
O后面没有I用了。既然后面的
O要有I,那能不能提前给他留出一个I不用呢?具体地,从后往前枚举,遇到
I就入队列,遇到O就弹出队头,与之配对。之后从前往后枚举,用一个数组标记是否用过这个位置,在枚举时统计能当前面
I或N的个数。遇到
O时,看他是否已经被配对且前面还有空闲的I或N,都满足则ans++。这个算法可以通过全部小样例和大样例,感觉应该对了吧。
其实并非,感觉上有反例,我写了一个对拍,拍了 就挂了。
观察一组简单的数据:
IOOIOII。显然答案应该为 ,但上述算法给出 。
简单分析可以发现,在枚举到 的
O时,算法错误地把他和 的I配了对,导致没法继续组成答案。而且,, 这两个配对完全没有用上。
这时有一个简单的补救方法:加一步反悔,把用不上的配对中的
I给上一个用,把靠前的I变成空闲的。显然空闲的I越靠前就越优,这样改不会更劣。也就是枚举到成功配对的
O的时候,如果前面没有可以用的空闲的I或N,就要做这个反悔。这样总该对了吧?
其实还没对,我继续跑对拍,发现在大约第 组出锅了。
发现 中所述并不完备,对于同一个
O,如果有多个已经计入答案可以反悔的,理应对最前面的一个反悔。于是我们做一些改进,用队列存储所有已经计入答案的
NOI,IOI中靠后的I,每次反悔时取出队头,再把新的I扔进队尾,显然队列内元素有序。最后发现对拍跑不出错来了,直接提交,喜提 pts。
CODE
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second int T,n,m; string s; int usd[1001000]; int q[1001000],fr=1,tl=0; int mtc[1001000];//match signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>s; s=' '+s; for(int i=n;i>=1;i--){ if(s[i]=='O'){ if(fr<=tl) mtc[i]=q[fr++]; } if(s[i]=='I') q[++tl]=i; } fr=1,tl=0; int ans=0,si=0;//si表示空闲的 I or N for(int i=1;i<=n;i++){ if(s[i]=='O'){ if(mtc[i]&&si) usd[mtc[i]]=1,si--,ans++,q[++tl]=mtc[i]; else if(mtc[i]&&!si&&ans){ int lst=q[fr++]; if(lst<i) si++; usd[mtc[i]]=1,usd[lst]=0; q[++tl]=mtc[i]; } } else if(!usd[i]) si++; } cout<<ans<<'\n'; return 0; } // NO NO ONOO I NN I III // I O O O I ONNIOIOINI // *****O*IOIONI // NOI O NO I NO O OIIII // INOOIOONNINIOII //部分反例和手玩过程
信息
- ID
- 900
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 51
- 已通过
- 10
- 上传者