UVA10273 Eat or Not to Eat?

题目传送门

分析：

由于每头“奶牛”周期不会超过 $10$，因此几只“奶牛”具有同样的产奶周期的概率很大。

而具有同样产奶周期的“奶牛”的“命运”是有紧密关联的，即任意一天有“奶牛”被卖，假设被卖的是这几只“奶牛”中的一只，那么它肯定是它们之中产奶最少的一只。

于是，可以将具有相同“命运”的“奶牛”们作为一个整体来维护，每次将它们之中产奶的最小值和其他整体进行比较，每次“奶牛”被卖后重新维护该组，即可大大减少计算量。

代码如下:

#include<bits/stdc++.h>
using namespace std;
int gcd_(int n,int m){
    return m==0 ? n : gcd_(m,n%m);
}
inline int read(int x = 0){//快读
    char ch = getchar();
    for(;ch < '0' || ch > '9' ; ch = getchar());
    for(;ch <= '9' && ch >= '0' ; ch = getchar()){
        x = (x<<1) + (x<<3)+ ch - '0';
    }
    return x;
}
int main(){
    int n,t;
    t = read();
    while(t--){
        n = read();
        multiset<pair<int,int> >cow[15][15];//pair保存产奶量和牛的编号
        int milk[1005][15]={0} , q[15]={0};
        for(int i=1,qq;i<=n;i++){
            qq = read();
            q[qq] = 1;
            for(int j=1,m; j <= qq; j++){
                milk[i][j] = read();
                cow[qq][j].insert(make_pair(milk[i][j],i));
            }
        }
        int cnt = 1;
        for(int i=1 ; i<=9; i++){//求所有周期的最小公倍数
            if(q[i]!=0)cnt = cnt*i/gcd_(cnt,i);//如果有这个周期
        }
        int last=0,sum=n;
        cnt*=2;
        for(int k=1; k<=cnt&&sum!=0; k++){
            int mmin=-1, mini=-1, minn=0x7FFFFFFF;
            for(int i=1; i<=10; i++){
                int j = (k-1)%i+1;
                multiset<pair<int,int> >::iterator ii = cow[i][j].begin();
                if(q[i]&&cow[i][j].size() >= 1){
                    if((*ii).first < minn){
                        mmin = (*ii).second;
                        minn = (*ii).first;
                        mini = i;
                        if(cow[i][j].size() > 1){
                            ii++;
                            if((*ii).first == minn) mmin = -1;
                        }
                    }
                    else if((*ii).first == minn) mmin = -1;
                }
                else if((*ii).first == minn) mmin = -1;
            }
            if(mmin != -1){
                last = k;
                for(int i=1; i<=mini; i++){
                    cow[mini][i].erase(cow[mini][i].find(make_pair(milk[mmin][i], mmin)));
                }
                sum--;
            }
        }
        cout << sum << " " << last << endl;
    }
    return 0;
}