首页 > 代码库 > UVA 10273 Eat or not to Eat?
UVA 10273 Eat or not to Eat?
直接暴力模拟 。以每次还未被删除的cnt[i]为一周期进行暴力模拟
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}int lcm(int a, int b) {if (a < b) swap(a,b);int tmp = gcd(a,b); return a / tmp * b;}#define MAXN 1010int N;int cnt[MAXN];int src[MAXN][20];bool killed[MAXN];int kill(int day){ int ans = 300,num = 0,st; for (int i = 1; i <= N; i++) if (!killed[i]) { int val = src[i][day % cnt[i]]; if (val == ans) num++; if (val < ans) { ans = val; st = i; num = 1; } } if (num == 1) return st; return 0;}int main(){ int T; scanf("%d",&T); while (T--) { scanf("%d",&N); for (int i = 1; i <= N; i++) { scanf("%d",&cnt[i]); for (int j = 1; j < cnt[i]; j++) scanf("%d",&src[i][j]); scanf("%d",&src[i][0]); } memset(killed,false,sizeof(killed)); int tot = 0, st = 1, ed,ans = 0; while (true) { bool flag = false; int tmp = 1; for (int i = 1; i <= N; i++) if (!killed[i]) tmp = lcm(tmp,cnt[i]); ed = st + tmp - 1; for (int i = st; i <= ed; i++) { int k = kill(i); if (k) { killed[k] = true; //printf("%d %d\n",k,i); tot ++; ans = i; flag = true; } } st = ed + 1; if (!flag || tot >= N) break; } printf("%d %d\n",N - tot,ans); } return 0;}
UVA 10273 Eat or not to Eat?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。