设为首页 加入收藏

TOP

uva 10273 Eat or Not to Eat?
2014-11-23 21:42:23 来源: 作者: 【 】 浏览:7
Tags:uva 10273 Eat Not


思路: 暴力求解
分析:
1 题目要求没有吃掉的奶牛的个数已经最后一次吃掉奶牛的天数
2 没有其它的方法只能暴力,对于n头牛的n个周期求最小公倍数,然后在2个公倍数之内暴力求解

代码:


#include
#include
#include
#include
#include
using namespace std;

const int MAXN = 1010;

int n , lcm;
vectorv[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();
    }
}

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇poj1673 下一篇hdu2128之BFS

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·【C语言】动态内存管 (2025-12-27 06:23:20)
·C语言中的内存管理 - (2025-12-27 06:23:16)
·C语言指南:C语言内 (2025-12-27 06:23:14)
·Redis on AWS:Elast (2025-12-27 04:19:30)
·在 Spring Boot 项目 (2025-12-27 04:19:27)