2289.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2289 on 2006-07-27 at 13:45:13 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int L = 32;
const int IN = 128, PN = 16;

class Ingredient {
public:
	char name[L];
	bool cer;
	int u, d;
	void make();
};
void Ingredient::make() {
	cer = false;
	scanf("%s", name);
	char c;
	while((c = getchar()) == ' ');
	if(c == '\n') return;
	else {
		ungetc(c, stdin);
		cer = true;
		scanf("%d%*c", &d); u = d;
	}
}

class Product {
private:
	void setIngredient();
public:
	int n;
	char name[L];
	Ingredient ing[IN];
	void make();
	pii range(char*) const;
};
void Product::make() {
	int i; scanf("%s %d", name, &n);
	for(i = 0; i < n; i++) ing[i].make();
	setIngredient();
}
void Product::setIngredient() {
	int i, j, k, low = 1, high = 100, total = 100;
	int d[IN], u[IN];
	for(i = 0, j = n-1; i < n; i++, j--) {
		if(ing[i].cer) high = ing[i].u;
		else u[i] = ing[i].u = high;
		if(ing[j].cer) low = max(ing[j].d, 1);
		else d[j] = ing[j].d = low;
		total -= ing[j].d;
	}
	for(i = 0; i < n; i++) {
		if(ing[i].cer) continue;
		bool beg = false;
		int tsum = total;
		for(j = k = 0; j < n; j++) {
			if(ing[j].cer) { beg = false; continue; }
			if(j == i) beg = true;
			if(beg) k++;
			else tsum -= u[j]-d[j];
		}
		if(tsum > 0) ing[i].d += (tsum+k-1)/k;
	}
	for(i = n-1; i >=0; i--) {
		if(ing[i].cer) continue;
		for(k = 0, j = i; j >= 0 && !ing[j].cer; j--, k++);
		if(k*(u[i]-d[i]) <= total) ing[i].u = u[i];
		else ing[i].u = d[i]+total/k;
	}
}
pii Product::range(char* iname) const {
	int i;
	for(i = 0; i < n; i++)
		if(!strcmp(iname, ing[i].name))
			return pii(ing[i].d, ing[i].u);
	return pii(0, 0);
}

int main()
{
	int n, q, i, j, k;
	Product pro[PN];

	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) pro[i].make();
		scanf("%d", &q);
		for(i = 0; i < q; i++) {
			char intro[L], name[L]; scanf("%s %s", intro, name);
			pii rng[PN];
			bool e[PN] = { false }, pn = false;
			for(j = 0; j < n; j++) rng[j] = pro[j].range(name);
			for(j = 0; j < n; j++)
				for(k = 0; k < n; k++)
					if(intro[0] == 'm' && rng[j].second < rng[k].first) e[j] = true;
					else if(intro[0] == 'l' && rng[k].second < rng[j].first) e[j] = true;
			for(j = 0; j < n; j++)
				if(!e[j]) { printf("%s%s", pn ? " " : "", pro[j].name); pn = true; }
			putchar('\n');
		}
	}

	return 0;
}