首页 > 试题广场 >

香槟塔

[编程题]香槟塔
  • 热度指数：3306 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
节日到啦，牛牛和妞妞邀请了好多客人来家里做客。
他们摆出了一座高高的香槟塔，牛牛负责听妞妞指挥，往香槟塔里倒香槟。
香槟塔有个很优雅的视觉效果就是如果这一层的香槟满了，就会从边缘处往下一层流去。
妞妞会发出两种指令，指令一是往第x层塔内倒体积为v的香槟，指令二是询问第k层塔香槟的体积为多少。
告诉你香槟塔每层香槟塔的初始容量，你能帮牛牛快速回答妞妞的询问吗？

输入描述:
第一行为两个整数n，m。表示香槟塔的总层数和指令条数。
第二行为n个整数ai，表示每层香槟塔的初始容量。
第三行到第2+m行有两种输入，一种输入是“2 x v”表示往第x层倒入体积为v的香槟；另一种输入是“1 k”表示询问第k层当前有多少香槟。
1 <= n, m <= 1000。
1 <= n ,m <= 200000，1 <= ai ,v <= 1000000000。


输出描述:
对于每个询问，输出一个整数，表示第k层香槟的容量。
示例1

输入

1 2
8
2 1 9
1 1

输出

8
示例2

输入

5 4
1 2 2 10 1
1 3
2 2 5
2 4 3
1 4

输出

0
4
算法知识视频讲解
添加回答
Java
何止hz头像 何止hz
暴力法，耗时比较长 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: coderjjp
 * @Date: 2020-05-08 17:47
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line1[] = br.readLine().split(" ");
        int n = Integer.valueOf(line1[0]);//层数
        int m = Integer.valueOf(line1[1]);//总指令数
        int V[] = new int[n+1];
        String[] line2 = br.readLine().split(" ");
        for (int i = 0; i < n; i++)
            V[i+1] = Integer.valueOf(line2[i]);
        int cur[] = new int[n+1];//初始体积
        while (m-- > 0){
            String linex[] = br.readLine().split(" ");
            int order[] = new int[linex.length];
            for (int i = 0; i < linex.length; i++)
                order[i] = Integer.valueOf(linex[i]);
            if (order[0] == 1)
                System.out.println(cur[order[1]]);
            else{
                int rem = order[2];
                for (int i = order[1]; i <= n && rem > 0; i++){
                    if (cur[i] == V[i])
                        continue;
                    if (rem >= V[i]-cur[i]){
                        rem = rem - (V[i] - cur[i]);
                        cur[i] = V[i];
                    }else {
                        cur[i] += rem;
                        rem = 0;
                    }
                }
            }
        }
    }
}


发表于 2020-05-08 20:45:13 回复(0)
Java
热爱学习的小怪兽。头像 热爱学习的小怪兽。

注意：不能用for循环，for循环的时间复杂度太大，要用while

import java.util.*;
public class Main{
   public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int ceng=sc.nextInt();
        int zhiling=sc.nextInt();
        int[] churong=new int[ceng];
        int[] xiangrong=new int[ceng];
        int j=0;

        while(j<ceng){
            int A1=sc.nextInt();
            churong[j]=A1;
            xiangrong[j]=0;
            j++;

        }
        int z=0;
        while(z<zhiling){
            int gu=sc.nextInt();
            if(gu==1){
                int k=sc.nextInt();
                int l=xiangrong[k-1];
                System.out.println(l);
            }else{
                int b=sc.nextInt();
                int x=b-1;
                int v=sc.nextInt();
                while(v>0&&x<ceng){
                    //如果 杯子已有的水<杯子 并且v<杯子-水
                    if(xiangrong[x]<churong[x]&&v<churong[x]-xiangrong[x]){
                        xiangrong[x]=xiangrong[x]+v;
                        v=0;
                    }
                    else {
                        //v=v-（杯子-水）
                        v=v-(churong[x]-xiangrong[x]);
                        xiangrong[x]=churong[x];
                        x++;
                    }
                }
            }
            z++;

        }
   }
}
发表于 2019-09-20 16:59:22 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 数组 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 高级结构 网易 2019 拼多多集团-PDD Java工程师
上传者：小小
难度：
2条回答 9778浏览

热门推荐

通过挑战的用户

查看代码

相关试题

香槟塔

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号