程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> V - Ice-cream Tycoon(線段樹)

V - Ice-cream Tycoon(線段樹)

編輯：C++入門知識

V - Ice-cream Tycoon(線段樹)

有兩種操作，ARRIVE a b 表示單價為b的冰激凌的進貨數目為a，BUY a b表示同學共拿b元錢，想買a個盡量便宜的冰激凌，若能購買到，輸出HAPPY，否則輸出UNHAPPY”

操作挺簡單，單點更新然後push_up。但是寫起來感覺挺麻煩。

首先先讀入所有的操作，將進貨的冰激凌單價離散化，建立線段樹，然後按讀入順序，對於ARRIVE操作，更新相應的冰激凌的數目及價格，對“BUY操作，優先搜索左子樹，即盡量買便宜的，若能購買，再去更新相應區間的數目及價錢。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define eps 1e-12
#define PI acos(-1.0)
#define PP pair
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100010;
const int mod = 1000000007;

struct Info
{
    char str[10];
    LL num;
    LL mon;
} info[maxn];

struct node
{
    int l,r;
    LL num; //冰激凌數目
    LL sum;//總價錢
    LL price;//一種冰激凌的單價
} tree[maxn*4];

LL x[maxn];

int Binsearch(int l, int r, LL key)
{
    int mid,low = l,high = r;
    while(high >= low)
    {
        mid = (low + high) >> 1;
        if(x[mid] == key)
            return mid;
        if(x[mid] > key)
            high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

void build(int v, int l, int r)
{
    tree[v].l = l;
    tree[v].r = r;
    tree[v].num = tree[v].sum = tree[v].price = 0;
    if(l == r)
        return;
    int mid = (l+r)>>1;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
}

void push_down(int v)
{
	if(tree[v].l == tree[v].r)
		return;
	if(tree[v].num == 0 && tree[v].sum == 0)
	{
		tree[v*2].num = tree[v*2+1].num = 0;
		tree[v*2].sum = tree[v*2+1].sum = 0;
	}
}

void push_up(int v)
{
	tree[v].num = tree[v*2].num + tree[v*2+1].num;
	tree[v].sum = tree[v*2].sum + tree[v*2+1].sum;
}

void update(int v, int pos, LL num, LL mon, LL t)
{
    if(tree[v].l == tree[v].r)
    {
        if(tree[v].price == 0)
            tree[v].price = mon;
		tree[v].num += num;
		tree[v].sum += t;
        return;
    }
	push_down(v); //重點，不要遺漏。
    int mid = (tree[v].l + tree[v].r)>>1;
    if(pos <= mid)
        update(v*2,pos,num,mon,t);
    else
        update(v*2+1,pos,num,mon,t);
	push_up(v);
}

void update_1(int v, LL num, LL sum)
{
	tree[v].num -= num;
	tree[v].sum -= sum;
	if(tree[v].l == tree[v].r)
		return;
	if(tree[v*2].num >= num)
		update_1(v*2,num,sum);
	else
	{
		LL tmp1 = num - tree[v*2].num;
		LL tmp2 = sum - tree[v*2].sum;
		tree[v*2].num = 0;
		tree[v*2].sum = 0;
		update_1(v*2+1,tmp1,tmp2);
	}
}

LL query(int v, LL num)
{
    if(tree[v].num < num)
        return -1;
    if(tree[v].num == num)
    {
        return tree[v].sum;
    }
    if(tree[v].l == tree[v].r)
    {
        return tree[v].price * num;
    }
    if(tree[v*2].num >= num)
        return query(v*2,num);
    else
    {
        LL res = query(v*2+1,num-tree[v*2].num);
        return tree[v*2].sum + res;
    }
}

int main()
{
    int t1,t2,k;
    LL a,b;
    char ch[10];
    t1 = 0;
    t2 = 0;
    while(~scanf(%s %I64d %I64d,ch,&a,&b))
    {
        struct Info tmp;
        strcpy(tmp.str,ch);
        tmp.num = a;
        tmp.mon = b;
        info[++t1] = tmp;
        if(ch[0] == 'A')
            x[++t2] = b;
    }
    sort(x+1,x+1+t2);
    k = 1;
    for(int i = 2; i <= t2; i++)
    {
        if(x[i] != x[i-1])
            x[++k] = x[i];
    }
    build(1,1,k);

    for(int i = 1; i <= t1; i++)
    {

        if(info[i].str[0] == 'A')
        {
            int pos = Binsearch(1,k,info[i].mon);
            LL t = info[i].num*info[i].mon;
            update(1,pos,info[i].num,info[i].mon,t);//單點更新冰激凌的數目，價格和單價
        }
        else
        {
            LL res = query(1,info[i].num);
            if(res == -1) //總數目小於購買數目
                printf(UNHAPPY
);
            else
            {
                if(info[i].mon >= res)
				{
					printf(HAPPY
);
					update_1(1,info[i].num,res);//能購買，就去更新相應區間的數目及價錢
				}
				else printf(UNHAPPY
);
            }
        }
    }

    return 0;
}