Coding Beans: 3月 2016

原題連結
一道並查集的頗直覺的題目
難點大概就只有在有沒有想到要用Disjoint Set去做吧......
對於已經滿的vessel i ，執行 fa[i] <- findset(i+1) ，直觀上就是將每個相鄰的滿vessel連接起來，已達到快速查詢可用vessel的效果。

細節上要注意水流到地上的case要做好，不然很容易WA或是TLE。

#include<cstdio>
#define LL long long
using namespace std;
const int maxn=200000+5;
int fa[maxn],cap[maxn],cur[maxn];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {fa[i]=i;scanf("%d",cap+i);}
    fa[n]=n;
    scanf("%d",&m);
    for(int i=0,type,a,b;i<m;i++)
    {
        scanf("%d",&type);
        if(type==1)
        {
            scanf("%d%d",&a,&b);a--;
            a=findset(a);
            for(;b && a!=n;)
            {
                if(cap[a]-cur[a]>b) cur[a]+=b,b=0;
                else // cap[a]-cur[a]<=b
                {
                    b-=cap[a]-cur[a];
                    cur[a]=cap[a];
                    fa[a]=findset(a+1);
                    a=findset(a);
                }
            }
        }
        else
        {
            scanf("%d",&a);a--;
            printf("%d\n",cur[a]);
        }
    }
}

2016年3月15日 星期二

2016年3月14日 星期一

2016年3月13日 星期日

2016年3月12日 星期六

2016年3月11日 星期五

2016年3月10日 星期四

2016年3月9日 星期三

2016年3月8日 星期二

2016年3月7日 星期一

2016年3月6日 星期日

2016年3月5日 星期六

2016年3月4日 星期五

2016年3月3日 星期四

2016年3月2日 星期三

2016年3月1日 星期二

2016年3月15日星期二

2016年3月14日星期一

2016年3月13日星期日

2016年3月12日星期六

2016年3月11日星期五

2016年3月10日星期四

2016年3月9日星期三

2016年3月8日星期二

2016年3月7日星期一

2016年3月6日星期日

2016年3月5日星期六

2016年3月4日星期五

2016年3月3日星期四

2016年3月2日星期三

2016年3月1日星期二