Editorial for VOI 12 Bài 3 - Điều động
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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 flashmt
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; int n,c[10100],t[10100],l[10100],r[10100]; int possible(int T) { for (int i=1;i<=n;i++) l[i]=r[i]=0; for (int i=0;i<n;i++) l[max(1,c[i]-T/t[i])]++, r[min(n,c[i]+T/t[i])]++; for (int i=1;i<=n;i++) { l[i]+=l[i-1]; r[i]+=r[i-1]; if (l[i]<i || r[i]>i) return 0; } return 1; } int main() { cin >> n; for (int i=0;i<n;i++) cin >> c[i] >> t[i]; int low=0,high=100000000,ans=high; while (low<=high) { int mid=(low+high)>>1; if (possible(mid)) ans=mid, high=mid-1; else low=mid+1; } cout << ans << endl; }
Code mẫu của happyboy99x
#include<algorithm> #include<iostream> #include<vector> #include<queue> using namespace std; const int N = 10000; int c[N], t[N], n; bool ok(int timeLimit) { vector<pair<int, int> > limit (n); for(int i = 0; i < n; ++i) limit[i] = make_pair(max(0, c[i] - timeLimit / t[i]), min(n - 1, c[i] + timeLimit / t[i])); sort(limit.begin(), limit.end()); priority_queue<int> q; for(int pos = 0, x = 0; pos < n; ++pos) { while(x < n && limit[x].first <= pos) q.push(-limit[x++].second); if(q.empty() || pos > -q.top()) return false; q.pop(); } return true; } void enter() { cin >> n; for(int i = 0; i < n; ++i) cin >> c[i] >> t[i], --c[i]; } void solve() { int low = 0, high = 1e9; while(low < high) { int mid = (low + high) >> 1; if(ok(mid)) high = mid; else low = mid + 1; } cout << low << '\n'; } int main() { ios::sync_with_stdio(false); enter(); solve(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> #define X first #define Y second const int N = 10005; const int oo = trunc(1e9); using namespace std; int c[N], t[N]; int n, res; ii List[N]; void Init(int lim) { int Range, Left, Right; for(int i=1; i<=n; i++) { Range = lim / t[i]; Left = max(c[i] - Range, 1); Right = min(c[i] + Range, n); List[i] = ii(Left, Right); } sort(List + 1, List + 1 + n); } bool Slide() { int pos = 1, R; priority_queue<int, vector<int>, greater<int> > Q; for(int i=1; i<=n; i++) { while (pos <= n && List[pos].X <= i) Q.push(List[pos++].Y); if (!Q.size()) return false; R = Q.top(); Q.pop(); if (R < i) return false; } return true; } int main() { scanf("%d\n", &n); for(int i=1; i<=n; i++) scanf("%d %d\n", &c[i], &t[i]); int l = 0, r = oo, m; while (l <= r) { m = (l + r) >> 1; Init(m); if (Slide()) { res = m; r = m - 1; } else l = m + 1; } printf("%d", res); return 0; }
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); const int MN = 100111; int n, x[MN], t[MN]; pair<int,int> a[MN]; multiset< pair<int,int> > s; bool check(int v) { FOR(i,1,n) { int can = v / t[i]; a[i] = MP(max(x[i] - can, 1), min(x[i] + can, n)); } sort(a+1, a+n+1); s.clear(); int j = 0; FOR(i,1,n) { while (j < n && a[j+1].F <= i) { ++j; s.insert(MP(a[j].S, a[j].F)); } if (s.empty()) return false; pair<int,int> cur = *s.begin(); s.erase(s.begin()); if (cur.F < i) return false; } return true; } int main() { scanf("%d", &n); FOR(i,1,n) scanf("%d%d", &x[i], &t[i]); int l = 0, r = 1000111000, res = r; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) { res = mid; r = mid - 1; } else l = mid + 1; } cout << res << endl; return 0; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<math.h> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> #include<ctype.h> #define ep 0.00001 #define maxn 10011 #define oo 1111111111 #define modunlo 35000 #define mod 1000000007 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define fi first #define se second //#define g 9.81 double const PI=4*atan(1.0); //#include<conio.h> using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; int n,c[maxn],t[maxn],T; vector <int> V1,V2; bool check(int x){ V1.clear(); V2.clear(); for(int i = 0; i < n; i++){ T = x/t[i]; V1.push_back(max(1,c[i]-T)); V2.push_back(min(n,c[i]+T)); } sort(V1.begin(),V1.end()); sort(V2.begin(),V2.end()); for(int i = 0; i < n; i++){ if(V1[i] > i+1 || V2[i] < i+1) return false; } return true; } int main(){ // freopen("input.in","r",stdin); // freopen("output.out","w",stdout); scanf("%d",&n); for(int i = 0; i < n; i++){ scanf("%d %d",&c[i],&t[i]); } int u = 0, v = oo , r; while( u < v){ r = (u + v)/2; if(check(r)) v = r; else u = r + 1; } printf("%d",u); }
Code mẫu của skyvn97
#include<cstdio> #include<queue> #include<vector> #define MAX 10010 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define FORE(i,v) for(__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) using namespace std; const int INF=(int)1e8+7; int c[MAX]; int t[MAX]; vector<int> seg[MAX]; int n; void init(void) { scanf("%d",&n); FOR(i,1,n) { scanf("%d",&c[i]); scanf("%d",&t[i]); } } bool ok(int x) { FOR(i,1,n) seg[i].clear(); FOR(i,1,n) { int ran=x/t[i]; seg[max(1,c[i]-ran)].push_back(min(n,c[i]+ran)); } priority_queue<int,vector<int>,greater<int> > q; while (!q.empty()) q.pop(); FOR(i,1,n) { FORE(it,seg[i]) q.push(*it); while (!q.empty() && q.top()<i) q.pop(); if (q.empty()) return (false); q.pop(); } return (true); } void process(void) { int l=0; int r=INF; while (true) { if (l==r) { printf("%d",r); return; } if (r-l==1) { if (ok(l)) printf("%d",l); else printf("%d",r); return; } int m=(l+r)>>1; if (ok(m)) r=m; else l=m+1; } } int main(void) { init(); process(); return 0; }
Comments