首页 > 代码库 > UVA 239 - Tempus et mobilius. Time and motion(置换周期)
UVA 239 - Tempus et mobilius. Time and motion(置换周期)
UVA 239 - Tempus et mobilius. Time and motion
题目链接
题意:这题题意也是吊得飞起,看了老半天,大概是这样:
有一个放球的队列,和3个轨道(说白了就是栈),一个容纳5,1个12,1个12,每1分钟队列出一个小球,放入栈,如果放入5的满了,就把5的放回队列,头一个放入12的,如果12的满了,就把12的放回队列,头一个放入另一个12的栈,如果又满了,就全部放回队列(头一个最后放回),问多少天之后,队列中小球会回复原来的状态
思路:先是模拟求出一天的情况,对应一个置换,然后就是求置换中循环的最大公倍数即可了
代码:
#include <stdio.h> #include <string.h> #include <queue> #include <stack> using namespace std; const int N = 7005; int n, next[N], vis[N]; long long gcd(long long a, long long b) { if (!b) return a; return gcd(b, a % b); } long long lcm(long long a, long long b) { return a / gcd(a, b) * b; } int main() { while (~scanf("%d", &n) && n) { queue<int> Q; stack<int> mins, fives, hours; for (int i = 0; i < n; i++) Q.push(i); for (int t = 0; t < 1440; t++) { int now = Q.front(); Q.pop(); if (mins.size() == 4) { for (int i = 0; i < 4; i++) { Q.push(mins.top()); mins.pop(); } if (fives.size() == 11) { for (int i = 0; i < 11; i++) { Q.push(fives.top()); fives.pop(); } if (hours.size() == 11) { for (int i = 0; i < 11; i++) { Q.push(hours.top()); hours.pop(); } Q.push(now); } else hours.push(now); } else fives.push(now); } else mins.push(now); } for (int i = 0; i < n; i++) { next[i] = Q.front(); Q.pop(); } memset(vis, 0, sizeof(vis)); long long ans = 1; for (int i = 0; i < n; i++) { if (!vis[i]) { long long cnt = 1; vis[i] = 1; int t = next[i]; while (!vis[t]) { cnt++; vis[t] = 1; t = next[t]; } ans = lcm(ans, cnt); } } printf("%d balls cycle after %lld days.\n", n, ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。