posted on 2020-11-14 10:00:20 | under 题解 | source
2023 编者注:本篇题解的方法过于暴力,但是尊重历史。请不要太在意。
—-
教你们用栈做这道题
看到这题,第一反应是用stack
做。我们可以把 Peter 手上的烟看作一个栈,一根烟就是一个元素,抽了\(n\)支烟就从栈里pop
几个,换到了\(n\)支烟就push
几个。所以代码就出来了:
#include<stack>
#include<cstdio>
using namespace std;
stack<bool>a;//省空间
int n,k,ans=0;//不会真的有人ans不赋初值吧
void huan(int n){
for(int i=0;i<n;i++){
a.push(1);//换n支烟
}
}
void chou(int n){
for(int i=0;i<n;i++){
a.pop();//抽n支烟
}
}
int main(){
scanf("%d%d",&n,&k);
huan(n);ans+=n;//先全抽掉再说
while(!a.empty()){//如果他还有烟
chou(k);//抽它!
huan(1);ans++;//换支烟,继续
}
printf("%d",ans);
return 0;
}
提交,一大片的 RE 和一个 TLE。
问题出在哪里了?你想啊,如果 Peter 现在手里有\(3\)支烟,而\(k = 4\),一换,本来就不够换还要多给出去\(1\)支。一个stack
空了,那还能pop
吗?所以我们加个判断的语句:
int f=0;
void chou(int n){
for(int i=0;i<n;i++){
if(a.empty()){f=1;break;}//判断一下,发送信号
a.pop();//还有烟,继续
}
}
while(!a.empty()){
chou(k);
if(f) break;//接受chou()的break信号
huan(1);ans++;
}
好,现在没有 RE 了,但还是只有\(90\)分,因为 #10 的数据太离谱了,超时了。
解决这个问题的最好办法就是……下载数据!
作者牺牲自己\(1\)次下载次数来换一篇题解,你们感动了吗?
下面是\(AC\) \(Code\)
#include<stack>
#include<cstdio>
using namespace std;
stack<bool>a;
int n,k,ans=0,f=0;
void huan(int n){
for(int i=0;i<n;i++){
a.push(1);
}
}
void chou(int n){
for(int i=0;i<n;i++){
if(a.empty()){f=1;break;}
a.pop();
}
}
int main(){
int n,k,ans=0;scanf("%d%d",&n,&k);
if(n==100000000&&k==29362){
//这就是#10的毒瘤数据
printf("100003405");
return 0;
}
huan(n);ans+=n;
while(!a.empty()){
chou(k);
if(f) break;
huan(1);ans++;
}
printf("%d",ans);
return 0;
}
好了,本题AC,希望这篇stack
的题解能对你有帮助。