[POI 19 Stage 2] Vouchers

作法：

直接模擬就可以了，對每個 x 要記錄一個 st[ x ] ，代表 x 的倍數裡面從 x 到 st[ x ] 大小的糖果包都已經被拿走了。還有當拿的糖果包大小 > 1000000 的時候就可以直接跳掉了，因為不影響哪些人拿到有裝神祕禮物的糖果包，這樣就可以保證複雜度是 O( C * logC ) 了，其中 C 是數字的最大值。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
int vis[maxn],st[maxn] ;
vector<LL> ans ;
main()
{
     int n ; scanf("%d",&n) ;
     while(n--)
     {
          int x ; scanf("%d",&x) ;
          vis[x]=1 ;
     }
     scanf("%d",&n) ;
     LL cnt=0 ;
     while(n--)
     {
          int x ; scanf("%d",&x) ;
          int i=st[x]+x ;
          for(int j=1;j<=x && i<maxn;i+=x)
          {
               if(vis[i]==2) continue ;
               if(vis[i]==1) ans.push_back(cnt+j) ;
               vis[i]=2 ; j++ ;
          }
          st[x]=i-x ;
          cnt+=x ;
     }
     printf("%d\n",ans.size()) ;
     for(int i=0;i<ans.size();i++) printf("%lld\n",ans[i]) ;
}