1933.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1933 on 2006-06-16 at 19:24:38 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int CN = 8, GN = 24;

int main()
{
	int m[GN], cs[GN][CN], idx[GN];
	bool e[CN];
	int i, j, g, n;
	
	while(scanf("%d %d", &g, &n) != EOF && g != 0) {
		memset(idx, 0, sizeof(idx)); memset(e, false, sizeof(e));
		for(i = 0; i < g; i++) {
			scanf("%d", &m[i]);
			for(j = 0; j < n; j++) scanf("%d", &cs[i][j]);
		}
		for(i = 1; i < n; i++) {
			int pn[CN] = { 0 };
			for(j = 0; j < g; j++) {
				while(e[cs[j][idx[j]]]) idx[j]++;
				pn[cs[j][idx[j]]] += m[j];
			}
			int en = -1, pd = 1<<28;
			for(j = n; j > 0; j--)
				if(!e[j] && pd > pn[j]) { pd = pn[j]; en = j; }
			e[en] = true;
		}
		for(i = 1; e[i]; i++);
		printf("%d\n", i);
	}
	
	return 0;
}