P9810题解

· · 题解

题目传送门

修改内容：对解法进一步的说明补充。将【中文标点符号】与【英文、数字、公式或汉字】之间的多余空格删去。

题目大意：

此题输入 k 个数，在遇到输入的值为 0 的时候则需要弹出最后一个进来的数。否则加入该数。

算法实现：

80 pts 方法

首先将所有的数的值累加放到 sum1 中再利用循环找到前面每一个不为 0 的数的值加到 sum2 中去，并将加到 sum2 过的值修改成 0 。最后在算出答案为 sum1- sum2 。

上代码：

#include<bits/stdc++.h>
using namespace std;
int k,last,sum1,sum2,a[100010];
int read() {
    int f=1,x=0;
    char ch=getchar();
    for(; ch<'0'||ch>'9'; ch=getchar()) if (ch=='-') f=-1;
    for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-48;
    return x*f;
}
int main(){
    k=read();
    a[1]=read();sum1=a[1];
    for(int i=2;i<=k;i++){
        a[i]=read();sum1+=a[i];
        if (a[i]==0) {
            for(int j=i;j>=1;j--)
                if (a[j]!=0) {
                    sum2+=a[j];
                    a[j]=0;
                    break;
                }
        }
    }
    printf("%d\n",sum1-sum2);
    return 0;
}

测评记录

100 pts 方法

因为栈是后进先出，用栈可以快速的解决这个问题，若 {a_i} = 0 ，则根据后进先出原则，便可以将最后一个进入的元素弹出。若 {a_i} > 0 则放进栈中。最后再将栈中的所有的数都弹出并进行累加，得到的结果 ans 便是答案。

上代码：

#include<bits/stdc++.h>
using namespace std;
stack<int> q;
int ans;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x;
        cin>>x;
        if (x==0) q.pop();
        else q.push(x);
    }
    int len=q.size();
    for(int i=1;i<=len;i++) {
        int x=q.top();
        ans+=x;
        q.pop();
    }
    printf("%d\n",ans);
    return 0;
}//祝大家noip rp++;