Hướng dẫn giải của Lập lịch trên 2 máy
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 flashmt
const fi=''; fo=''; maxn=10000; type ar=array[1..maxn] of longint; var a,b,a1,b1,d1,a2,b2,d2:ar; n,n1,n2:longint; re:int64; procedure rf; var i:longint; begin read(n); for i:=1 to n do read(a[i]); for i:=1 to n do read(b[i]); n1:=0; n2:=0; for i:=1 to n do if a[i]<=b[i] then begin inc(n1); a1[n1]:=a[i]; b1[n1]:=b[i]; d1[n1]:=i; end else begin inc(n2); a2[n2]:=a[i]; b2[n2]:=b[i]; d2[n2]:=i; end; end; procedure sort(l,r:longint); var i,j,x,t:longint; begin i:=l; j:=r; x:=a1[(i+j) shr 1]; repeat while a1[i]<x do i:=i+1; while a1[j]>x do j:=j-1; if i<=j then begin t:=b1[i]; b1[i]:=b1[j]; b1[j]:=t; t:=a1[i]; a1[i]:=a1[j]; a1[j]:=t; t:=d1[i]; d1[i]:=d1[j]; d1[j]:=t; i:=i+1; j:=j-1; end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure sort1(l,r:longint); var i,j,x,t:longint; begin i:=l; j:=r; x:=b2[(i+j) shr 1]; repeat while b2[i]>x do i:=i+1; while b2[j]<x do j:=j-1; if i<=j then begin t:=b2[i]; b2[i]:=b2[j]; b2[j]:=t; t:=a2[i]; a2[i]:=a2[j]; a2[j]:=t; t:=d2[i]; d2[i]:=d2[j]; d2[j]:=t; i:=i+1; j:=j-1; end; until i>j; if i<r then sort1(i,r); if l<j then sort1(l,j); end; procedure pr; var i:longint; x:int64; begin re:=0; x:=0; for i:=1 to n1 do begin x:=x+a1[i]; if x>re then re:=x; re:=re+b1[i]; end; for i:=1 to n2 do begin x:=x+a2[i]; if x>re then re:=x; re:=re+b2[i]; end; writeln(re); for i:=1 to n1 do write(d1[i],' '); for i:=1 to n2 do write(d2[i],' '); end; begin assign(input,fi); reset(input); assign(output,fo); rewrite(output); rf; sort(1,n1); sort1(1,n2); pr; close(input); close(output); end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N 10005 int a[N], b[N], x[N], y[N], n; int cmp1( const int & x, const int & y ) { return a[x] < a[y]; } int cmp2( const int & x, const int & y ) { return b[x] > b[y]; } int main() { scanf("%d",&n); rep(i,n) scanf("%d",a+i); rep(i,n) scanf("%d",b+i); int cx = 0, cy = 0; rep(i,n) if( a[i] <= b[i] ) x[cx++] = i; else y[cy++] = i; sort(x,x+cx,cmp1); sort(y,y+cy,cmp2); copy(y,y+cy,x+cx); int ta = a[x[0]], tb = ta + b[x[0]]; fo(i,1,n-1) { ta += a[x[i]]; if( ta >= tb ) tb = ta + b[x[i]]; else tb += b[x[i]]; } printf("%d\n%d", tb, x[0]+1); fo(i,1,n-1) printf(" %d", x[i]+1); printf("\n"); return 0; }
Code mẫu của ladpro98
#include <iostream> #include <cstdio> #include <algorithm> #define FOR(i, a, b) for(int i = (a); i < (b); i++) const int N = 100005; using namespace std; int n; struct II { int X, Y, id; } a[N]; bool cmp(const II &a, const II &b) {return min(a.X, b.Y) < min(a.Y, b.X);} int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n; FOR(i, 0, n) cin >> a[i].X; FOR(i, 0, n) cin >> a[i].Y; FOR(i, 0, n) a[i].id = i + 1; sort(a, a + n, cmp); int startA = 0, startB = 0, finishA = 0, finishB = 0; FOR(i, 0, n) { startA = finishA; finishA = startA + a[i].X; startB = max(finishA, finishB); finishB = startB + a[i].Y; } cout << finishB << endl; FOR(i, 0, n) cout << a[i].id << ' '; cout << endl; return 0; }
Code mẫu của RR
import java.util.*; import java.io.*; import java.math.*; class Job { int a, b, index; Job() { } Job(int a, int b, int i) { this.a = a; this.b = b; this.index = i; } } class JobComparatorA implements Comparator <Job> { public int compare(Job A, Job B) { if (A == null && B == null) return 0; if (A == null) return 1; if (B == null) return -1; if (A.a < B.a) return -1; else if (A.a > B.a) return 1; else return 0; } } class JobComparatorB implements Comparator <Job> { public int compare(Job A, Job B) { if (A == null && B == null) return 0; if (A == null) return 1; if (B == null) return -1; if (A.b > B.b) return -1; else if (A.b < B.b) return 1; else return 0; } } public class Main { public static int timeA = 0, timeB = 0; static void JobExecute(int a, int b) { timeA += a; timeB = Math.max(timeB, timeA) + b; } public static void main(String args[]) { try { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()), n1 = 0, n2 = 0; Job[] list1 = new Job[n]; Job[] list2 = new Job[n]; String ta[] = br.readLine().split(" "); String tb[] = br.readLine().split(" "); for(int i = 0; i < n; i++) { int a = Integer.parseInt(ta[i]); int b = Integer.parseInt(tb[i]); if (a < b) list1[n1++] = new Job(a, b, i+1); else list2[n2++] = new Job(a, b, i+1); } Comparator <Job> c1 = new JobComparatorA(); Comparator <Job> c2 = new JobComparatorB(); Arrays.sort(list1, c1); Arrays.sort(list2, c2); for(int i = 0; i < n1; i++) JobExecute( list1[i].a, list1[i].b ); for(int i = 0; i < n2; i++) JobExecute( list2[i].a, list2[i].b ); System.out.println(timeB); for(int i = 0; i < n1; i++) System.out.print( list1[i].index + " " ); for(int i = 0; i < n2; i++) System.out.print( list2[i].index + " " ); } catch (Exception e) { } } }
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> void quickSorttang(int A[],int X[],int b[], int lower,int upper) { int x = A[(lower + upper) / 2]; int i = lower; int j = upper; do{ while(A[i] < x) i ++; while (A[j] > x) j --; if (i <= j) { int tg=A[i]; A[i]=A[j]; A[j]=tg; int tgx=X[i]; X[i]=X[j]; X[j]=tgx; int tgb=b[i]; b[i]=b[j]; b[j]=tgb; i ++; j --; } }while(i <= j); if (j > lower) quickSorttang(A,X,b, lower, j); if (i < upper) quickSorttang(A,X,b, i, upper); } void quickSortgiam(int A[],int X[],int b[], int lower,int upper) { int x = A[(lower + upper) / 2]; int i = lower; int j = upper; do{ while(A[i] > x) i ++; while (A[j] < x) j --; if (i <= j) { int tg=A[i]; A[i]=A[j]; A[j]=tg; int tgx=X[i]; X[i]=X[j]; X[j]=tgx; int tgb=b[i]; b[i]=b[j]; b[j]=tgb; i ++; j --; } }while(i <= j); if (j > lower) quickSortgiam(A,X,b, lower, j); if (i < upper) quickSortgiam(A,X,b, i, upper); } main() { int n,a[10001],b[10001],a1[10001],b1[10001],a2[10001],b2[10001],x1[10001],x2[10001],u=0,v=0; long A[10001],B[10001]; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) { if(a[i]<=b[i]) { u++; a1[u]=a[i]; b1[u]=b[i]; x1[u]=i; } else { v++; a2[v]=a[i]; b2[v]=b[i]; x2[v]=i; } } quickSorttang(a1,x1,b1,1,u); quickSortgiam(b2,x2,a2,1,v); if(u>0) { A[1]=a1[1]; B[1]=a1[1]+b1[1]; } else { A[1]=a2[1]; B[1]=a2[1]+b2[1]; } for(int i=1;i<=u;i++) { A[i]=A[i-1]+a1[i]; if(A[i]>B[i-1]) B[i]=A[i]+b1[i]; else B[i]=B[i-1]+b1[i]; } for(int i=u+1;i<=u+v;i++) { A[i]=A[i-1]+a2[i-u]; if(A[i]>B[i-1]) B[i]=A[i]+b2[i-u]; else B[i]=B[i-1]+b2[i-u]; } printf("%ld\n",B[n]); for(int i=1;i<=u;i++) printf("%d ",x1[i]); for(int i=1;i<=v;i++) printf("%d ",x2[i]); //getch(); }
Code mẫu của khuc_tuan
import java.io.*; import java.util.*; public class Main { static class CV { public int a,b,i,t; } public static void main(String[] Args) throws Exception { BufferedReader kb=new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(kb.readLine()); CV[] c=new CV[n]; for(int i=0;i<n;++i) c[i]=new CV(); StringTokenizer st=new StringTokenizer(kb.readLine()); for(int i=0;i<n;++i) c[i].a = Integer.parseInt(st.nextToken()); st=new StringTokenizer(kb.readLine()); for(int i=0;i<n;++i) c[i].b = Integer.parseInt(st.nextToken()); for(int i=0;i<n;++i) { c[i].i=i; if(c[i].a<c[i].b) c[i].t=1; else c[i].t=2; } Arrays.sort(c, new Comparator<CV>() { public int compare(CV x,CV y) { if(x.t!=y.t) return x.t-y.t; if(x.t==1) return x.a-y.a; if(x.t==2) return y.b-x.b; return 0; } }); int ta=0,tb=0; for(int i=0;i<n;++i) { ta += c[i].a; if(tb<ta) tb=ta; tb += c[i].b; } System.out.println(Math.max(ta,tb)); for(int i=0;i<n;++i) System.out.print(c[i].i+1+" "); System.out.println(); } }
Bình luận
include <bits/stdc++.h>
using namespace std;
bool cmp( pair<int,int> A, pair<int,int> B) { return A.second > B.second; }
int main() { int n; cin >> n;
}