P6704 [COCI2010-2011#7] GITARA(栈)
发布日期:2021-05-08 21:51:56 浏览次数:14 分类:精选文章

本文共 785 字,大约阅读时间需要 2 分钟。

这道题可利用栈的思想来解决。每当有一个新的数字被输入时,检查栈顶的数字。如果栈顶的数字大于等于当前输入的数字,就弹出栈顶的数字,直到栈顶的数字小于当前输入的数字或栈为空。然后将当前数字压入栈中。通过这种方法,可以计算出总共弹出了多少次。

具体步骤如下:

  • 初始化栈数组sum和a。
  • 读取输入的数字n和p。
  • 对于每个输入的数字对(x, y):
    • 进入while循环,检查栈顶是否大于等于1,并且栈顶的数字大于y。
    • 如果条件满足,弹出栈顶(sum[x]减一),并计数加一。
    • 继续循环,直到栈顶小于等于y或栈为空。
    • 如果栈顶的数字等于y,跳过当前循环。
    • 否则,将y压入栈中(sum[x]加一),计数加一。
  • 通过上述步骤,可以计算出总共弹出的次数。

    以下是实现代码:

    #include 
    #include
    using namespace std;int n, p, x, y, s, sum[7], a[7][300005];int main() { scanf("%d%d", &n, &p); for (int i = 1; i <= n; i++) { scanf("%d%d", &x, &y); while (sum[x] >= 1 && a[x][sum[x]] > y) { sum[x]--; s++; } if (a[x][sum[x]] == y) continue; a[x][++sum[x]] = y; s++; } printf("%d", s); return 0;}

    这个代码通过模拟栈的操作,确保每次输入的数字都能正确处理,计算出总共弹出的次数。

    上一篇:2020.9.12 SSL普及组模拟(第1题)(字符串)
    下一篇:T145300 【2020.8.24NOIP模拟赛】这是一棵树吗?(图论)

    发表评论

    最新留言

    表示我来过!
    [***.240.166.169]2025年03月21日 23时57分50秒