TLE的一般代码

Ryan123 • 2年前

`#include <bits/stdc++.h> using namespace std; vector CC[1010]; int cow[1001]; int Cy[1010]; //一般代码 int GCD(int a,int b) { return b==0?a:GCD(b,a%b); } int main() { int t; cin>>t; while(t--) {

int n;
cin>>n;
vector<int> CC[1010];
for(int i=0; i<n; i++)
{
  cin>>Cy[i];
  for(int j=0,x; j<Cy[i]; j++)
  {
    cin>>x;
    CC[i].push_back(x);
  }
}
int length=Cy[0];

for(int i=1; i<n; i++)
  length=length*Cy[i]/GCD(length,Cy[i]);
int last=-1,cnt=n;
memset(cow,0,sizeof(cow));
for(int day=0; day<=length*2 && cnt!=0; day++)
{
  int Min=0x7fffffff,rec=-1;
  for(int j=0; j<n; j++)
  {
    if(cow[j]) continue;
    int now=CC[j][day%Cy[j]];
    if(now==Min)
      rec=-1;
    if(now<Min)
    {
      Min=now;
      rec=j;
    }
  }
  if(rec!=-1)
  {
    cow[rec]=1;
    last=day;
    cnt--;
  }
}
cout<<cnt<<' '<<last+1<<'\n';

} return 0; } `

评论:

正解

#include <bits/stdc+.h>
using namespace std;

int n, t;

inline int gcd(int a, int b) {
    while(b^=a^=b^=a%=b);
    return a;
}

inline int read() {
    int x = 0;
    char c = getchar();
    for(; c<'0'||c>'9'; c=getchar());
    for(; c>='0'&&c<='9'; c=getchar())
        x = (x<<3)+(x<<1)+c-'0';
    return x;
}

struct mooooh {
    int milk, id;
    bool operator < (const mooooh a) const {
        return milk==a.milk ? id<a.id : milk<a.milk;
    }
};

int main() {
    t = read();
    while(t--) {
        n = read();
        multiset<mooooh> cow[11][11];
        int milk[1010][11] = {0};
        int zhouqi[11] = {0};
        for(int i=1,zq; i<=n; i++) {
            zq = read();
            zhouqi[zq] = 1;
            for(int j=1; j<=zq; j++) {
                milk[i][j] = read();
                cow[zq][j].insert({milk[i][j], i});
            }
        }
        int cnt = 1;
        for(int i=1; i<10; i++) {
            if(zhouqi[i])
                cnt = cnt*i/gcd(cnt, i);
        }
        int last = 0, num = n;
        cnt <<= 1;
        for(int k=1; k<=cnt&&num!=0; k++) {
            int mn_pos = -1, mn_id = -1, mn_milk = 0x7FFFFFFF;
            for(int i=1; i<=10; i++) {
                int j = (k-1)%i+1;
                if(zhouqi[i] && cow[i][j].size()>0) {
                    multiset<mooooh>::iterator ii = cow[i][j].begin();
                    if((*ii).milk < mn_milk) {
                        mn_pos = (*ii).id;
                        mn_id = i;
                        mn_milk = (*ii).milk;
                        if(cow[i][j].size()>1) {
                            ii++;
                            if((*ii).milk == mn_milk)
                                mn_pos = -1;
                        }
                    } else if((*ii).milk == mn_milk)
                        mn_pos = -1;
                }
            }
            if(mn_pos != -1) {
                last = k;
                for(int i=1; i<=mn_id; i++)
                    cow[mn_id][i].erase(cow[mn_id][i].find({milk[mn_pos][i], mn_pos}));
                num--;
            }
        }
        printf("%d %d\n", num, last);
    }
    return 0;
}

wangjiajian • 2年前