社区讨论
萌新WA:为什么我只有80分!为什么没有数据下载!
P3718[AHOI2017初中组] alter参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6z11ja
- 此快照首次捕获于
- 2025/11/20 13:08 4 个月前
- 此快照最后确认于
- 2025/11/20 13:08 4 个月前
CPP
#include<bits/stdc++.h>
#define ini(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define F(x,y,z) for(register int x=y;x<=z;++x)
#define D(x,y,z) for(register int x=y;x>=z;--x)
#define cint const int&
using namespace std;
const int MAXN=static_cast<int>(1e5)+100;
const long long INF=0x3f3f3f3f3f3f3f3f;
const int oo=0x3f3f3f3f;
const int MOD=2e5+1;
#define int long long
inline int read()
{
int x = 0, y = 1, c = getchar();
while (c>'9' || c<'0')
{
if (c == '-')y = -1;
c = getchar();
}
while (c >= '0'&&c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * y;
};
struct node{
int data,pos;
node(int d=0,int p=0):data(d),pos(p){}
};
class Deque{
private:
//#define node int
node que[MAXN];
int head,tail,_size;
public:
Deque():head(0),tail(0),_size(0){};
void push_back(const node&i){
que[tail++]=i;
_size++;
tail%=MOD;
}
void push_front(const node&i){
que[--head]=i;
_size++;
head%=MOD;
}
void pop_back(){
tail--;
_size--;
tail%=MOD;
}
void pop_front(){
head++;
_size--;
head%=MOD;
}
node front(){
return que[head];
}
node back(){
return que[tail-1];
}
int size(){
return _size;
}
bool empty(){
return !_size;
}
//#undef node
};
Deque q;
int light[MAXN];
inline bool check(cint len,cint n,cint k){
int cnt=0,pk=0,left=1;
F(i,1,n){
if(light[i]==light[left]){
cnt++;
}else{
cnt=1;
left=i;
}
if(cnt>len){
pk++;
cnt=0;
left=i+1;
}
if(pk>k){
return false;
}
}
if(pk>k){
return false;
}
return true;
}
signed main(){
int n=read(),k=read();
F(i,1,n){
int c=getchar();
while(c>'Z'||c<'A'){
c=getchar();
}
light[i]=(c=='N')?1:0;
}
int mid,left=0,right=MAXN;
while(left<right){
mid=(left+right)>>1;
if(check(mid,n,k)){
right=mid;
}else{
left=mid+1;
}
//cout<<left<<" "<<right<<endl;
}
printf("%lld",right);
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...