两道类似的题
考虑一个人应该能够观察的位置 ti,(ti+S)modT,(ti+2S)modT⋯ 这个应该是形成 gcd(S,T) 个环，每个环是长度 Tg 然后把同一个环的一起处理，把点放到环上，那么沿环的方向到下一个点为止应该都是归到这个点答案里面的
#include<cstdio> #include<cstdlib> #include<algorithm> #include<set> using namespace std; typedef long long ll; typedef pair<ll,ll> abcd; #define read(x) scanf("%I64d",&(x)) inline abcd EXGCD(ll a,ll b){ if (!b) return abcd(1,0); abcd t=EXGCD(b,a%b); return abcd(t.second,t.first-a/b*t.second); } inline ll Calc(ll a,ll b,ll p){ abcd t=EXGCD(a,p); ll d=t.first*a+t.second*p; return ((t.first%p+p)*(b/d))%p; } const int N=200005; ll n,S,T,g,C; ll a[N],_a[N]; int idx[N]; abcd t[N]; int tot; ll ans[N]; set<ll> Set; inline bool cmp(int x,int y){ return a[x]%g==a[y]%g?a[x]<a[y]:a[x]%g<a[y]%g; } int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(T); read(n); for (int i=1;i<=n;i++) read(_a[i]),S+=_a[i]; for (int i=1;i<n;i++) a[i]=(i?a[i-1]:0)+_a[i+1],idx[i]=i; g=__gcd(S,T); C=T/g; sort(idx,idx+n,cmp); for (int i=0,j;i<n;i=j+1){ j=i; while (j+1<n && a[idx[j+1]]%g==a[idx[i]]%g) j++; tot=0; for (int k=i;k<=j;k++){ int x=idx[k]; if (Set.count(a[x]%T)) continue; Set.insert(a[x]%T); t[++tot].first=Calc(S%T,(a[x]+T-a[x]%g)%T,T)%C; t[tot].second=x; } if (tot==1) ans[t[1].second]=C; else{ sort(t+1,t+tot+1); for (int k=1;k<tot;k++) ans[t[k].second]=((t[k+1].first+C-t[k].first)%C+C)%C; ans[t[tot].second]=((t[1].first+C-t[tot].first)%C+C)%C; } } for (int i=0;i<n;i++) printf("%I64d%c",ans[i],i==n-1?'\n':' '); return 0; }考虑如果一边某个人在时刻 t 被标记，那么至少 n 时刻后 (t+n)modm 号人也必然被标记，也就是一个环上求最早被访问到的距离，还是放到环上，到下一个点位置应该都是以这个点作为最优的 最后两边被访问到最晚的时间就是答案
#include<cstdio> #include<cstdlib> #include<algorithm> #include<set> using namespace std; typedef long long ll; typedef pair<ll,ll> abcd; #define read(x) scanf("%d",&(x)) inline abcd EXGCD(ll a,ll b){ if (!b) return abcd(1,0); abcd t=EXGCD(b,a%b); return abcd(t.second,t.first-a/b*t.second); } inline ll Calc(ll a,ll b,ll p){ abcd t=EXGCD(a,p); ll d=t.first*a+t.second*p; return ((t.first%p+p)*(b/d))%p; } const int N=200005; int S,T,g; int a[N],b[N]; ll ans; abcd t[N]; int _t; set<int> Set; inline bool cmp(abcd x,abcd y){ return x.first%g==y.first%g?(x.first==y.first?x.second<y.second:x.first<y.first):x.first%g<y.first%g; } abcd l[N]; int tot; inline void Solve(int S,int T,int *a,int *b){ _t=0; ll C=S/g; Set.clear(); for (int i=1;i<=*a;i++) t[++_t]=abcd(a[i],a[i]),Set.insert(a[i]); for (int i=1;i<=*b;i++) t[++_t]=abcd(b[i]%S,b[i]); sort(t+1,t+_t+1,cmp); int pnt=0; for (int i=1;i<=_t;i++) if (i==1 || t[i].first!=t[i-1].first) t[++pnt]=t[i]; _t=pnt; int last=-1; for (int i=1,j;i<=_t;i=j+1){ if (t[i].first%g!=last+1){ printf("-1\n"),exit(0); } last=t[i].first%g; j=i; while (j+1<=_t && t[i].first%g==t[j+1].first%g) j++; for (int k=i;k<=j;k++) t[k].first=Calc(T%S,(t[k].first+S-t[k].first%g)%S,S)%C; sort(t+i,t+j+1); if (i==j){ if (S/g==1 && Set.count((last+t[i].first*T)%S)) ans=max(ans,0LL); else ans=max(ans,t[i].second+(ll)(S/g-1)*T); }else{ for (int k=i;k<=j;k++){ if ((C+t[k==j?i:k+1].first-1-t[k].first)%C==0 && Set.count(last+t[i].first*T)) ans=max(ans,0LL); else ans=max(ans,(ll)(C+t[k==j?i:k+1].first-1-t[k].first)%C*T+t[k].second); } } } if (last!=g-1){ printf("-1\n"),exit(0); } } int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(S); read(T); g=__gcd(S,T); read(*a); for (int i=1;i<=*a;i++) read(a[i]); read(*b); for (int i=1;i<=*b;i++) read(b[i]); Solve(S,T,a,b); Solve(T,S,b,a); printf("%lld\n",ans); return 0; }