点击打开链接uva 10273
思路: 暴力求解
分析:
1 题目要求没有吃掉的奶牛的个数已经最后一次吃掉奶牛的天数
2 没有其它的方法只能暴力,对于n头牛的n个周期求最小公倍数,然后在2个公倍数之内暴力求解
代码:
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1010;
int n , lcm;
vector<int>v[MAXN];
bool isEat[MAXN];
int gcd(int a , int b){
return b == 0 ? a : gcd(b , a%b);
}
void init(){
memset(isEat , false , sizeof(isEat));
for(int i = 0 ; i < MAXN ; i++)
v[i].clear();
}
void solve(){
int index = 0;
int notEat = n;
int numDay = 0;
while(index < 2*lcm){
int min = 1<<30;
int minIndex = -1;
for(int i = 0 ; i < n ; i++){
if(!isEat[i]){
int size = v[i].size();
int tmp = v[i][index%size];
if(min > tmp){
min = tmp;
minIndex = i;
}
else{
if(min == tmp)
minIndex = -1;
}
}
}
index++;
if(minIndex != -1){
notEat--;
numDay = index;
isEat[minIndex] = true;
}
}
printf("%d %d\n" , notEat , numDay);
}
int main(){
int Case , m , x;
scanf("%d" , &Case);
while(Case--){
scanf("%d" , &n);
init();
bool isFirst = true;
for(int i = 0 ; i < n ; i++){
scanf("%d" , &m);
if(isFirst){
lcm = m;
isFirst = false;
}
lcm = lcm/gcd(lcm , m)*m;
while(m--){
scanf("%d" , &x);
v[i].push_back(x);
}
}
solve();
}
}
分享到:
相关推荐
UVA109的题解,经测试完全正确,还附有题解。
uva272
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
UVA 10474
uva最全ac代码
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
uva_trilearn2002 源代码
PDF试题
主要是uvaoj习题相关题目 练习题目
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)