他们摆出了一座高高的香槟塔，牛牛负责听妞妞指挥，往香槟塔里倒香槟。
香槟塔有个很优雅的视觉效果就是如果这一层的香槟满了，就会从边缘处往下一层流去。
妞妞会发出两种指令，指令一是往第x层塔内倒体积为v的香槟，指令二是询问第k层塔香槟的体积为多少。
告诉你香槟塔每层香槟塔的初始容量，你能帮牛牛快速回答妞妞的询问吗？
[编程题]香槟塔
- 热度指数：3238 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
节日到啦，牛牛和妞妞邀请了好多客人来家里做客。
他们摆出了一座高高的香槟塔，牛牛负责听妞妞指挥，往香槟塔里倒香槟。
香槟塔有个很优雅的视觉效果就是如果这一层的香槟满了，就会从边缘处往下一层流去。
妞妞会发出两种指令，指令一是往第x层塔内倒体积为v的香槟，指令二是询问第k层塔香槟的体积为多少。
他们摆出了一座高高的香槟塔，牛牛负责听妞妞指挥，往香槟塔里倒香槟。
香槟塔有个很优雅的视觉效果就是如果这一层的香槟满了，就会从边缘处往下一层流去。
妞妞会发出两种指令，指令一是往第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
/*思路：线段树维护区间剩余容量和，查询操作直接输出，
从x层倒入操作则二分查找倒入的液体能到达的层数r，此时x到r-1层剩余容量为0，故区间更新为0，
单点更新r层剩余容量 = x到r层总容量tmp - 导入液体总体积val
（时间长没写线段树，忘了懒惰标记怎么用了，参考下楼里某位dalao的标记。很好用哈哈
*/
#include <bits/stdc++.h>
#define lc rt << 1
#define rc rt << 1 | 1
#define LL long long
using namespace std;
const int AX = 2e5 + 666 ;
LL s[AX<<2] ; // 维护各层剩余容量和
int lazy[AX<<2];
LL v[AX] ;
int n , m ;
LL left_v , tmp ;
void pushUp( int rt ){
s[rt] = s[lc] + s[rc];
return ;
}
void pushDown( int rt ){
if( lazy[rt] != -1 ){
s[lc] = s[rc] = 0 ;
lazy[lc] = lazy[rc] = 1 ;
lazy[rt] = -1 ;
}
return ;
}
void build( int rt , int l , int r ){
if( l == r ){
scanf("%lld",&s[rt]);
v[l] = s[rt] ;
return ;
}
int mid = ( l + r ) >> 1 ;
build( lc , l , mid );
build( rc , mid + 1 , r );
pushUp(rt);
}
void update( int rt , int l , int r , int L , int R , int op ){
if( L > r || R < l ) return ;
if( L <= l && R >= r ){
if( op ){
s[rt] = 0 ;
lazy[rt] = 1 ;
}else s[rt] = left_v ;
return ;
}
int mid = ( l + r ) >> 1 ;
pushDown( rt ) ;
if( l <= mid ) update( lc , l , mid , L , R , op );
if( R > mid ) update( rc , mid + 1 , r , L , R , op );
pushUp(rt) ;
}
LL query( int rt , int l , int r , int L , int R ){
if( L <= l && R >= r ) return s[rt] ;
int mid = ( l + r ) >> 1 ;
LL ans = 0 ;
pushDown( rt );
if( L <= mid ) ans += query( lc , l , mid , L , R ) ;
if( R > mid ) ans += query( rc , mid + 1 , r , L , R );
return ans ;
}
int getR( int l , int r , int x , int val ){ // 查找从x层倒，能满（四声）到哪一层为止
while( l <= r ){
int mid = ( l + r ) >> 1 ;
if( query( 1 , 1 , n , x , mid ) >= val ) r = mid - 1;
else l = mid + 1 ;
}
tmp = query( 1 , 1 , n , x , l ); //查询被倒入液体触及的所有层总容量
return l ;
}
int main(){
memset( lazy , -1 , sizeof(lazy) );
cin >> n >> m ;
build( 1 , 1 , n ) ;
int op , x ;
LL val ;
while( m-- ){
scanf("%d",&op);
if( op == 1 ){
scanf("%d",&x);
printf("%lld\n",v[x] - query( 1 , 1 , n , x , x ) );
}else{
scanf("%d%lld",&x,&val);
int r = getR( x , n , x , val ) ;
left_v = tmp - val ;
if( left_v <= 0 ){ //正好倒满或倒满地上了
update( 1 , 1 , n , x , r , 1 );
}else{
if( r == 1 ) update( 1 , 1 , n , 1 , 1 , 0 ); //第一层都倒不满
else{ //x到r-1层被倒满，剩余体积设为0，r层剩余left_v体积 = tmp(x到r层总容量)-val(总共倒入体积)
update( 1 , 1 , n , x , r - 1 , 1 ) ;
update( 1 , 1 , n , r , r , 0 );
}
}
}
}
return 0 ;
}
编辑于 2020-02-10 11:44:57
回复(1)
注意：不能用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)
Python Solution
假设第 层初始状态值为
，则装满的情况为该层状态值达到
。
假如第1层容积为2，则初始状态值为-2，倒入体积3的酒，则状态值归0，剩余体积1的酒向下流动。
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
st = [-i for i in a]
all_ml = [[int(i) for i in input().split()] for i in range(m)]
def pour(st, ml):
'''香槟塔的第x层到体积v的酒'''
x = ml[1]-1
v = ml[2]
while True:
v = v + st[x]
if v < 0:
st[x] = v
break
else:
st[x] = 0
x += 1
if x == len(st):
break
return st
def ask(a, st, ml):
'''k层装酒量=k层容积+k层状态值'''
k = ml[1]
print(a[k-1]+st[k-1])
for ml in all_ml:
if ml[0] == 2:
st = pour(st, ml)
else:
ask(a, st, ml)
编辑于 2019-08-28 15:53:44
回复(0)
/*
判断，循环。哭了，同样的程序python死活超时
*/
#include <bits/stdc++.h>
using namespace std;
#define N 200001
int a[N], b[N];
int main(void)
{
//freopen("input.txt", "r", stdin);
int n, m, op, x, v, k;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
while(m--) {
scanf("%d", &op);
if(op == 1) {
scanf("%d", &k);
printf("%d\n", b[k]);
} else {
scanf("%d%d", &x, &v);
while(x <= n && v > 0) {
if(a[x] - b[x] < v) {
v -= a[x] - b[x];
b[x] = a[x];
x++;
} else {
b[x] += v;
v = 0;
}
}
}
}
return 0;
}
发表于 2019-07-18 20:06:36
回复(0)
创建一个每层已到入香槟容积的数组，然后直接模拟倒香槟的过程就可以了。
n, m = map(int, input().strip().split()) a = list(map(int, input().strip().split())) # 初始情况下每一层被占用的容积为0 occupy = [0]*n for _ in range(m): temp = list(map(int, input().strip().split())) if len(temp) == 3: op, x, v = temp else: op, x = temp if op == 2: # 倒香槟操作 idx = x - 1 # 初始层号 while v and idx < n: if v + occupy[idx] > a[idx]: # 如果要倒的香槟和这一层已经被倒的体积超过了这一层的容积，就要向下流 v -= a[idx] - occupy[idx] # 向下流的体积 occupy[idx] = a[idx] # 更新本层被占用的容积 idx += 1 # 向下更新层号 if idx == n: break else: # 更新本层被占用的容积 occupy[idx] = v + occupy[idx] # 否则没有向下层流的体积 v = 0 else: # 询问操作 print(occupy[x - 1])
发表于 2021-01-30 18:38:45
回复(0)
静态链表
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <forward_list>
#define left (now<<1)
#define right ((now<<1)+1)
#define mid ((l + r) >> 1)
#define midmid ((r + mid) >> 1)
#define LONG_LONG_MIN -9223372036854775808ll
#define LONG_LONG_MAX 9223372036854775807ll
using namespace std;
typedef long long int ll;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
int n,m,nxt[MAXN],pre[MAXN];
ll now[MAXN],a[MAXN];
void init(){
for(int i = 1; i <= n + 1; ++i){
now[i] = 0; nxt[i] = i + 1; pre[i] = i - 1;
}
}
int main(){
scanf("%d%d",&n,&m); init();
for(int i = 1; i <= n; ++i){
scanf("%lld",&a[i]);
}
a[n + 1] = LONG_LONG_MAX / 2ll;
for(int i = 1; i <= m; ++i){
int command; scanf("%d",&command);
if(command == 2){
int x; ll v; scanf("%d%lld",&x,&v);
while(v > 0){
ll p = a[x] - now[x];
if(p >= v){
now[x] += v; v = 0;
}else{
now[x] = a[x]; v -= p;
nxt[pre[x]] = nxt[x];
pre[nxt[x]] = pre[x];
x = nxt[x];
}
}
}else{
int x; scanf("%d",&x);
printf("%lld\n",now[x]);
}
}
return 0;
}
发表于 2019-09-15 13:44:42
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,c,x,y;
cin>>n>>m;
int a[n+1],b[n+1];
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=0;i<m;i++){
cin>>c;
if(c==1){
cin>>x;
cout<<b[x]<<endl;
}else{
cin>>x>>y;
int t = a[x]-b[x];
while(y>t && x<=n){
b[x] += t;
if(x<=n){
y -= t;
x++;
t = a[x] - b[x];
}else
break;
}
if(x<=n)
b[x] += y;
}
}
return 0;
}
发表于 2019-08-27 01:21:36
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m,q,x,v,k;
cin>>n>>m;
int a[n],b[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
b[i]=0;
}
while(m--)
{
cin>>q;
if(q==1)
{
cin>>k;
cout<<b[k-1]<<endl;
}
if(q==2)
{
cin>>x>>v;
x--;
while(x<n&&v>0)
{
if ((a[x]-b[x])<v)
{
v -= a[x] - b[x];
b[x] = a[x];
x++;
}
else
{
b[x] += v;
v = 0;
}
}
}
}
return 0;
}
发表于 2019-07-11 21:23:33
回复(0)
二分+线段树，O(nlog^2n)解决
用线段树维护每层当前还能装下的体积。对于操作1，直接查询。对于操作2，先二分出从当前层能装满至哪里，然后将这一段容量置为0，最后剩下的单点修改一下就行了。
#include <bits/stdc++.h>
#define ls o*2
#define rs o*2+1
using namespace std;
const int N = 2e5+7;
int x,y,v,n;
long long O[N<<2],vol[N];
bool laz[N<<2];
void build(int o,int l,int r){
if(l==r){
scanf("%lld",&vol[l]);
O[o] = vol[l];
}else{
int mid = l+(r-l)/2;
build(ls,l,mid);
build(rs,mid+1,r);
O[o] = O[ls]+O[rs];
}
}
void pushdown(int o){
if(laz[o]){
O[ls] = O[rs] = 0;
laz[ls] = laz[rs] = 1;
laz[o] = 0;
}
}
void update(int o,int l,int r,int op){
if(x>r||y<l)return;
if(x<=l&&y>=r){
if(op==1){
laz[o] = 1;
O[o] = 0;
}
else O[o] = v;
}else{
int mid = l+(r-l)/2;
pushdown(o);
if(x<=mid)update(ls,l,mid,op);
if(y>mid)update(rs,mid+1,r,op);
O[o] = O[ls]+O[rs];
}
}
long long query(int o,int l,int r,int L,int R){
if(L<=l&&R>=r)return O[o];
else{
int mid = l+(r-l)/2;
long long ans = 0;
pushdown(o);
if(L<=mid)ans += query(ls,l,mid,L,R);
if(R>mid)ans += query(rs,mid+1,r,L,R);
return ans;
}
}
int find_pos(int l,int r,long long &res){
int mid;
while(l<r){
mid = l+(r-l)/2;
if(query(1,1,n,x,mid)<v)l = mid+1;
else r = mid;
}
res = query(1,1,n,x,l);
return l;
}
int main(){
int m;
scanf("%d %d",&n,&m);
build(1,1,n);
while(m--){
int op;
scanf("%d",&op);
if(op==1){
scanf("%d",&x);
printf("%lld\n",vol[x]-query(1,1,n,x,x));
}else{
long long res = 0;
scanf("%d %d",&x,&v);
y = find_pos(x,n,res);
v = res - v;
if(res!=0){
if(y==n)update(1,1,n,1);
else{
if(y==1){
x = y;
update(1,1,n,0);
}
else{
y--;update(1,1,n,1);
y++;x = y;
update(1,1,n,0);
}
}
}
else update(1,1,n,1);
}
}
return 0;
}
发表于 2019-04-26 10:36:04
回复(0)
可以参考并查集中的路径压缩，维护每个杯子下一个可以装水的杯子
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<int,int> next_layer;
int dfs(int layer,int v,vector<int>& cur,vector<int>& volume){
if(layer==volume.size()) return layer;
int tmp=volume[layer]-cur[layer];
if(tmp>=v){
cur[layer]+=v;
return layer;
}
cur[layer]=volume[layer];
next_layer[layer]=dfs(next_layer[layer],v-tmp,cur,volume);
return next_layer[layer];
}
int main(){
int n,m;
cin>>n>>m;
vector<int> volume(n+1);
vector<int> cur(n+1,0);
for(int i=1;i<=n;++i) cin>>volume[i];
for(int i=1;i<=n;++i) next_layer[i]=i+1;
while(m--){
int op;
cin>>op;
if(op==1){
int layer;
cin>>layer;
cout<<cur[layer]<<endl;
}
else{
int layer,v;
cin>>layer>>v;
if(volume[layer]-cur[layer]>=v) cur[layer]+=v;
else{
next_layer[layer]=dfs(layer,v,cur,volume);
}
}
}
return 0;
}
编辑于 2020-07-28 14:11:04
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[n][2];
for(int i=0;i<n;i++){
arr[i][0] = sc.nextInt();
}
for(int i=0;i<m;i++){
int o = sc.nextInt();
if(o==1){
int x = sc.nextInt()-1;
System.out.println(arr[x][1]);
}else{
int x = sc.nextInt()-1;
int v = sc.nextInt();
while(v>0 && x<n){
if(v <= arr[x][0]){
arr[x][1] += v;
arr[x][0] -= v;
v = 0;
//x++;
}else{
v -= arr[x][0];
arr[x][1] += arr[x][0];
arr[x][0] = 0;
x++;
}
}
}
}
}
}
}
发表于 2020-07-21 22:36:12
回复(0)
// 38行代码结束战斗，C++
#include <iostream>
#include <vector>
using namespace std;
int main(){
//输入数据
int numLayer, numCmd;
cin >> numLayer >> numCmd;
vector<int> volume(numLayer, 0), used(numLayer, 0);
for (int i=0;i<numLayer;++i)
cin >> volume[i];
while (numCmd--){
int cmd;
cin >> cmd;
//如果是查询
if (cmd == 1){
int where;
cin >> where;
cout << used[where-1] << endl;
}
//如果是灌水
else if (cmd == 2){
int where, amount;
cin >> where >> amount;
while (amount > 0){
//1.边界判断：全都满了
if (where > numLayer) break;
//2.如果不够装满当前层
if (amount <= volume[where-1] - used[where-1]){
used[where-1] += amount;
amount = 0;
}
//3.如果当前层满了，但是还有剩余
else{
amount -= volume[where-1] - used[where-1];
used[where-1] = volume[where-1];
++where;
}
}
}
}
return 0;
}
比较简单，跟着题目意思走就行
发表于 2020-07-15 18:19:18
回复(0)
暴力法，耗时比较长
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)
为什么感觉和上面做的不是一题?是数据变少了么？
import copy n,m = map(int,input().split()) nums = list(map(int,input().split())) nums = [0]+nums flag = copy.deepcopy(nums) for _ in range(m): op = list(map(int,input().split())) if len(op)==3: k,v= op[1],op[2] index = k while v>0 and index<n: if v>flag[index]: v = v- flag[index] flag[index] = 0 index+=1 else: flag[index] = flag[index]-v v = 0 else: k = op[1] print(nums[k] - flag[k])
发表于 2020-04-17 19:06:56
回复(0)
var line = readline().split(" ");
var n = line[0];
var m = line[1];
var arr = readline().split(" ").map(Number);
var resArr = [];
var i = m;
while(i>0){
var zl = readline()
zl = zl?zl.split(" ").map(Number):[]
if(zl.length>1){
var x = zl[1]-1
if(zl[0]==1){
console.log(resArr[x]?resArr[x]:0)
}else if(zl[0]==2){
var v = zl[2]
for(var j=x;j<n;j++){
resArr[j]=resArr[j]?resArr[j]:0;
if(resArr[j]+v>arr[j]){
v = resArr[j]+v-arr[j]
resArr[j] = arr[j]
}else{
resArr[j] += v;
break;
}
}
}
}
i--;
}
var n = line[0];
var m = line[1];
var arr = readline().split(" ").map(Number);
var resArr = [];
var i = m;
while(i>0){
var zl = readline()
zl = zl?zl.split(" ").map(Number):[]
if(zl.length>1){
var x = zl[1]-1
if(zl[0]==1){
console.log(resArr[x]?resArr[x]:0)
}else if(zl[0]==2){
var v = zl[2]
for(var j=x;j<n;j++){
resArr[j]=resArr[j]?resArr[j]:0;
if(resArr[j]+v>arr[j]){
v = resArr[j]+v-arr[j]
resArr[j] = arr[j]
}else{
resArr[j] += v;
break;
}
}
}
}
i--;
}
发表于 2020-04-07 13:48:27
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//香槟塔总层数
int m = sc.nextInt();//指令条数
long[] a = new long[n];// 初始容量
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
long[] champagnes = new long[n];//塔的 Champagne 量
for (int i = 0; i < m; i++) {
int flag = sc.nextInt();
if (flag == 1) {
int k = sc.nextInt() - 1;//询问第 k 层
System.out.println(champagnes[k]);
} else {
int x = sc.nextInt() - 1;//往第 x 层倒 Champagne
long v = sc.nextLong();//倒入的 Champagne 体积
pourChampagne(x, v, a, champagnes);
}
}
}
private static void pourChampagne(int towerIndex, long volume, long[] a, long[] champagnes) {
if (towerIndex >= a.length) {
return;
}
long capacity = a[towerIndex];//当前层的容量
long champagne = champagnes[towerIndex];//当前层的 Champagne 量
if (champagne == capacity) {
pourChampagne(towerIndex + 1, volume, a, champagnes);
return;
}
if (champagne + volume <= capacity) {
champagnes[towerIndex] += volume;
} else {
long residual = volume - (capacity - champagne);//当前层填满后流入下一层的余量
champagnes[towerIndex] = capacity;
pourChampagne(towerIndex + 1, residual, a, champagnes);
}
}
}
发表于 2020-04-04 21:41:06
回复(0)
c,z=list(map(int,input().split(" "))) r1=list(map(int,input().split(" "))) r2=[0 for i in range(c)] re=[] while z>0: in1=list(map(int,input().split(" "))) if in1[0]==1: re+=[r2[in1[1]-1]] elif in1[0]==2: while in1[1]<=c : k=in1[1]-1 if r1[k]==r2[k]: in1[1]+=1 continue if r1[k]>r2[k]: r2[k]=r2[k]+in1[2] if r2[k]>=r1[k]: in1[2]=r2[k]-r1[k] r2[k]=r1[k] in1[1]+=1 else:break z-=1 for i in re: print(i)
发表于 2019-09-08 22:58:23
回复(3)
n, m = map(int, input().split()) a = [int(i) for i in input().split()] b = [0 for i in range(n)] for i in range(m): order = [int(j) for j in input().split()] if order[0] == 1: print(b[order[1]-1]) else: k = 0 while b[order[1]+k-1]+order[2] > a[order[1]+k-1] and order[1]+k < n: order[2] = order[2] - (a[order[1]+k-1]-b[order[1]+k-1]) b[order[1]+k-1] = a[order[1]+k-1] k += 1 b[order[1] + k-1] += min(order[2], (a[order[1]+k-1]-b[order[1] + k-1]))
发表于 2019-09-06 22:33:30
回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main(void){
int n, m, oper, i, v, tmp_vol;
cin>>n>>m;
vector<int> volume(n, 0), contain(n, 0);
for(int i = 0; i < n; ++i)
cin>>volume[i];
while(m--){
cin>>oper>>i;
--i;
if(oper == 1)
cout<<contain[i]<<endl;
else{
cin>>v;
while(v + contain[i] >= volume[i] && i < n){
v = v + contain[i] - volume[i];
contain[i] = volume[i];
//写在上一句语句前面
//v = v + contain[i] - volume[i];
++i;
}
//用+=而不是=
if(i < n)
contain[i] += v;
}
}
return 0;
} 数组volume表示每层香槟塔的容积，contain表示每层香槟塔实际装酒的体积，初始化全为0
模拟倒香槟的操作：
- 规范输入下标，i=i-1
- 当前倒入香槟的第i层装酒量加上倒入体积v大于等于该层容积时，contain[i]=volume[i]表示该层已经装满，溢出到下一层的装酒量为v+contain[i]-volume[i]，转3;当前层没有溢出或者i=n，转4
- ++i，i < n时进入下一层的模拟，转2，i >= n时已经模拟到最后一层，转4
- i < n表示上一层溢出的酒还没装满本层，给它续上，否则已经到了最后一层，溢出再多酒都没用，都洒地上浪费了
发表于 2019-08-19 10:58:43
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] arr = new int[n + 1];
int[] cur = new int[n + 1];
int[] mark = new int[n + 1];
for(int i = 1; i <= n; i++) {
arr[i] = scanner.nextInt();
cur[i] = 0;
mark[i] = i;
}
while(m-- > 0) {
int option = scanner.nextInt();
if(option == 1) {
int k = scanner.nextInt();
System.out.println(cur[k]);
}
else if(option == 2){
int x = scanner.nextInt();
int v = scanner.nextInt();
while(v != 0) {
x = findMark(arr, cur, mark, n, x);
if(x == 0) break;
int gap = Math.min(arr[x] - cur[x], v);
cur[x] += gap;
v -= gap;
}
}
}
}
public static int findMark(int[] arr, int[] cur, int[] mark, int n, int x) {
if(x == n + 1) return 0;
if(arr[x] != cur[x]) return x;
else return mark[x] = findMark(arr, cur, mark, n, x + 1);
}
}
发表于 2019-08-18 15:08:14
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-10-11 19:59:40 -
2022-09-03 18:31:08
-
2022-08-28 09:45:03 -
2022-08-26 10:55:25
-
2022-08-20 11:38:41
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
