Hướng dẫn giải của PERIOD
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của happyboy99x
#include<algorithm> #include<iostream> #include<cassert> #include<cstdio> #include<limits> #include<queue> using namespace std; const int N = 5000000; long long a[2 * N]; int original[N]; int n, p, q, m, delta; long long brute() { long long res = numeric_limits<long long>::max(); for(int i = 0; i < n; ++i) { long long cost = numeric_limits<long long>::min(); for(int j = 0; j < n; ++j) cost = max(cost, original[(i + j) % n] + (j + 1LL) * delta); res = min(res, cost); } return res; } int main() { ios::sync_with_stdio(false); cin >> n >> delta >> p >> q >> m; for(int i = 0; i < n; ++i) a[i] = original[i] = p * (i + 1LL) % m + q; copy(a, a + n, a + n); for(int i = 0; i < 2 * n; ++i) a[i] += (i + 1LL) * delta; deque<int> q; long long res = numeric_limits<long long>::max(); for(int i = 0; i < 2 * n; ++i) { while(!q.empty() && a[i] >= a[q.back()]) q.pop_back(); while(!q.empty() && q.front() <= i - n) q.pop_front(); q.push_back(i); if(i >= n - 1) res = min(res, a[q.front()] - 1LL * (i - n + 1) * delta); } cout << res << endl; return 0; }
Code mẫu của ladpro98
program periodnb; uses math; const fi=''; maxN=10000007; type e=record val:int64; pos,carry:longint; end; var a,timer:array[-1..maxN] of int64; stack:array[-1..maxN] of e; n,head,tail:longint; p,q,m,time,res:int64; procedure input; var f:text; i:longint; begin assign(f,fi); reset(f); readln(f,n,time); readln(f,p,q,m); close(f); end; procedure init; var i:longint; t,pp:int64; begin pp:=0; p:=p mod m; for i:=1 to n do begin pp:=pp+p; while pp>=m do pp:=pp-m; a[i]:=pp + q; end; for i:=n+1 to n shl 1 do a[i]:=a[i-n]; timer[0]:=0; for i:=1 to n shl 1 do timer[i]:=timer[i-1]+time; for i:=1 to n do a[i]:=a[i]+timer[i]; head:=1;tail:=0; res:=high(int64); end; procedure process; var i:longint; begin for i:=1 to n do begin while (head<=tail) and (stack[tail].val<=a[i]) do dec(tail); inc(tail); stack[tail].val:=a[i]; stack[tail].pos:=i; stack[tail].carry:=0; end; for i:=n+1 to n shl 1 do begin inc(stack[tail].carry); if head<>tail then inc(stack[head].carry); while (head<=tail) and (stack[head].pos<=(i-n)) do begin inc(Head); if head<>tail then inc(stack[head].carry,stack[head-1].carry); end; a[i]:=a[i]+timer[n]; while (head<=tail) and ((stack[tail].val-timer[stack[Tail].carry])<=a[i]) do begin dec(tail); if head<tail then inc(stack[tail].carry,stack[tail+1].carry); end; inc(tail); stack[tail].val:=a[i]; stack[tail].pos:=i; stack[tail].carry:=0; res:=min(res,stack[head].val-timer[stack[Head].carry]); end; end; begin input; init; process; write(res); end.
Code mẫu của skyvn97
#include<algorithm> #include<cstdio> #include<iostream> #define MAX 5000500 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1) using namespace std; typedef long long ll; ll a[MAX]; ll maxleft[MAX]; ll maxright[MAX]; int n; ll d; void init(void) { ll p,m,q; cin >> n; cin >> d; cin >> p >> q >> m; FOR(i,1,n) a[i]=(p*i)%m+q+d*i; FOR(i,1,n) maxleft[i]=max(maxleft[i-1],a[i]); FORD(i,n,1) maxright[i]=max(maxright[i+1],a[i]); } void process(void) { ll res; ll tmp=0; FOR(i,1,n) tmp=max(tmp,a[i]); res=tmp; FOR(i,1,n-1) { tmp=max(maxleft[i]+d*(n-i),maxright[i+1]-d*i); res=min(res,tmp); } cout << res; } int main(void) { //freopen("PERIOD.INP","r",stdin); //freopen("PERIOD.OUT","w",stdout); init(); process(); return 0; }
Bình luận