[USACO 2013 Gold] Empty Stalls

我的作法蠻奇怪的，不過感覺上複雜度一樣是O(n) (?) ，官方解比我的好多了。

作法：

首先對每個位置，統計出有幾隻牛的目標是這個位置，接下來依序處理每個位置的牛。而對每個點 x ，都記錄一個數 ri[ x ] 代表 [ x+1 , ri[ x ] ) 這個區間裡的位置都被占領了，那麼在一隻牛尋找自己的位置的時候，就可以不用每格都掃過去，直接沿著 ri[ x ] 跳就好了，並且在放完目標是同一個位置的牛們之後，將沿路經過的位置的 ri 值都設成最後一個放牛的位置的 ri 值。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=3000000+10 ;
 
int num[maxn],ri[maxn] ;
bool used[maxn] ;
int tmp[maxn] ;
main()
{
    freopen("empty.in","r",stdin) ;
    freopen("empty.out","w",stdout) ;
    int n,k ; scanf("%d%d",&n,&k) ;
    for(int i=0;i<n;i++) ri[i]= ( i==n-1 ? 0 : i+1 ) ;
    while(k--)
    {
        int x,y,a,b ; scanf("%d%d%d%d",&x,&y,&a,&b) ;
        for(int i=1,j=(a+b)%n;i<=y;i++,j=(j+a)%n)
            num[j]+=x ;
    }
 
    for(int i=0;i<n;i++) if(num[i])
    {
        int cnt=0 , j=i ;
        for(int k=1;k<=num[i];j=ri[j])
        {
            if(!used[j]) k++ , used[j]=1 ;
            tmp[cnt++]=j ;
        }
        for(int k=0;k<cnt;k++) ri[tmp[k]]=j ;
    }
 
    for(int i=0;i<n;i++) if(!used[i])
        { printf("%d\n",i) ; return 0 ; }
}