首页 > 代码库 > SGU - 311 Ice-cream Tycoon(线段树)

SGU - 311 Ice-cream Tycoon(线段树)

2024-10-27 09:04:02   207人阅读

Description



You‘ve recently started an ice-cream business in a local school. During a day you have many suppliers delivering the ice-cream for you, and many students buying it from you. You are not allowed to set the prices, as you are told the price for each piece of ice-cream by the suppliers. 

The day is described with a sequence of queries. Each query can be either 
ARRIVE nc
, meaning that a supplier has delivered n pieces of ice-cream priced c each to you, or 
BUY nt
, meaning that a student wants to buy n pieces of ice-cream, having a total of t money. The latter is processed as follows: in case n cheapest pieces of ice-cream you have cost no more than t (together), you sell those n cheapest pieces to the student; in case they cost more, she gets nothing. You start the day with no ice-cream. 

For each student, output 
HAPPY
 if she gets her ice-cream, and 
UNHAPPY
if she doesn‘t.

Input

The input file contains between 1 and 10 5 queries (inclusive), each on a separate line. The queries are formatted as described above, either 
ARRIVE nc
 or 
BUY nt
, 1 ≤ n, c ≤ 10 6, 1 ≤ t ≤ 10 12.

Output

For each 
BUY
-query output one line, containing either the word 
HAPPY
 or the word 
UNHAPPY
 (answers should be in the same order as the corresponding queries).

Sample Input

sample input
sample output
ARRIVE 1 1
ARRIVE 10 200
BUY 5 900
BUY 5 900
BUY 5 1000

HAPPY
UNHAPPY
HAPPY


题意：一个商店，有两种操作：（1）ARRIVE n c表示进货n个，每一个c元。（2）BUY n t表示一个买货的人要买n个，一共拿了t元钱。假设如今店里的货的数量大于等于n且最廉价的n个的价格小于等于t则将最廉价的卖给他。否则不卖。

思路：离线的线段树，我们以价格作为结点，然后离散化，好久没做。看了final爷kuangbing的题解，注意的是优先处理最小的n个

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
typedef long long ll;
using namespace std;
const int maxn = 100010;

struct Node {
	int l, r;
	ll num;
	ll sum;
	int flag;
} segTree[maxn<<2];
int x[maxn];

void pushdown(int x) {
	if (segTree[x].l == segTree[x].r) 
		return;
	if (segTree[x].flag != -1) {
		segTree[lson(x)].sum = segTree[rson(x)].sum = 0;
		segTree[lson(x)].num = segTree[rson(x)].num = 0;
		segTree[lson(x)].flag = segTree[rson(x)].flag = 0;
		segTree[x].flag = -1;
	}
}

void pushup(int x) {
	if (segTree[x].l == segTree[x].r) 
		return;
	segTree[x].sum = segTree[lson(x)].sum + segTree[rson(x)].sum;
	segTree[x].num = segTree[lson(x)].num + segTree[rson(x)].num;
}

void build(int x, int l, int r) {
	segTree[x].r = r;
	segTree[x].l = l;
	segTree[x].sum = segTree[x].num = 0;
	segTree[x].flag = -1;
	if (l == r) return;
	int mid = l + r >> 1;
	build(lson(x), l, mid);
	build(rson(x), mid+1, r);
}

void Add(int i, int c, int n) {
	segTree[i].sum += (ll) c * n;
	segTree[i].num += n;
	if (x[segTree[i].l] == c && x[segTree[i].r] == c)
		return;
	pushdown(i);

	if (c <= x[segTree[lson(i)].r]) 
		Add(lson(i), c, n);
	else Add(rson(i), c, n);
}

ll query(int i, int n) {
	if (segTree[i].l == segTree[i].r) {
		return (ll) n * x[segTree[i].l];
	}
	pushdown(i);
	if (segTree[lson(i)].num >= n) 
		return query(lson(i), n);
	else return segTree[lson(i)].sum + query(rson(i), n-segTree[lson(i)].num);
}

void clear(int i, int n) {
	if (segTree[i].l == segTree[i].r) {
		segTree[i].num -= n;
		segTree[i].sum = segTree[i].num * x[segTree[i].l];
		return;
	}

	pushdown(i);
	if (segTree[lson(i)].num >= n)
		clear(lson(i), n);
	else {
		clear(rson(i), n-segTree[lson(i)].num);
		segTree[lson(i)].num = segTree[lson(i)].sum = 0;
		segTree[lson(i)].flag = 0;
	}
	pushup(i);
}

struct Query {
	char op[10];
	int n;
	ll c;
} q[maxn];

int main() {
	int n = 0;
	int tot = 0;
	while (scanf("%s%d%lld", q[n].op, &q[n].n, &q[n].c) != EOF) {
		if (q[n].op[0] == 'A')
			x[tot++] = q[n].c;
		n++;
	}
	sort(x, x+tot);
	tot = unique(x, x+tot) - x;
	build(1, 0, tot-1);

	for (int i = 0; i < n; i++) {
		if (q[i].op[0] == 'A')
			Add(1, q[i].c, q[i].n);
		else {
			if (segTree[1].num < q[i].n) 
				printf("UNHAPPY\n");
			else {
				if (query(1, q[i].n) > q[i].c)
					printf("UNHAPPY\n");
				else {
					printf("HAPPY\n");
					clear(1, q[i].n);
				}
			}
		}
	}
	return 0;
}


SGU - 311 Ice-cream Tycoon(线段树)


联系
我们