Hướng dẫn giải của Lập lịch trên 3 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=10010; var n,n1,n2:longint; re:int64; a,b,c,a1,b1,d1,a2,b2,d2:array[1..maxn] of longint; 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]); for i:=1 to n do read(c[i]); for i:=1 to n do if a[i]+b[i]<=b[i]+c[i] then begin inc(n1); a1[n1]:=a[i]+b[i]; b1[n1]:=b[i]+c[i]; d1[n1]:=i; end else begin inc(n2); a2[n2]:=a[i]+b[i]; b2[n2]:=b[i]+c[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:=a1[i]; a1[i]:=a1[j]; a1[j]:=t; t:=b1[i]; b1[i]:=b1[j]; b1[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:=a2[i]; a2[i]:=a2[j]; a2[j]:=t; t:=b2[i]; b2[i]:=b2[j]; b2[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,y:int64; begin x:=0; y:=0; re:=0; for i:=1 to n1 do begin x:=x+a[d1[i]]; if x>y then y:=x; y:=y+b[d1[i]]; if y>re then re:=y; re:=re+c[d1[i]]; end; for i:=1 to n2 do begin x:=x+a[d2[i]]; if x>y then y:=x; y:=y+b[d2[i]]; if y>re then re:=y; re:=re+c[d2[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 RR
import java.io.*; import java.util.*; class Job { int a, b, c, index; Job() { } Job(int a, int b, int c, int i) { this.a = a; this.b = b; this.c = c; this.index = i; } } class JobComparatorAB implements Comparator <Job> { public int compare(Job X, Job Y) { if (X == null && Y == null) return 0; if (X == null) return 1; if (Y == null) return -1; if (X.a + X.b < Y.a + Y.b) return -1; else if (X.a + X.b > Y.a + Y.b) return 1; else return 0; } } class JobComparatorBC implements Comparator <Job> { public int compare(Job X, Job Y) { if (X == null && Y == null) return 0; if (X == null) return 1; if (Y == null) return -1; if (X.b + X.c > Y.b + Y.c) return -1; else if (X.b + X.c < Y.b + Y.c) return 1; else return 0; } } public class Main { static int timeA = 0, timeB = 0, timeC = 0; static void JobExecute(int a, int b, int c) { timeA += a; timeB = Math.max(timeA, timeB) + b; timeC = Math.max(timeB, timeC) + c; } public static void main(String args[]) { try { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); String[] ta = br.readLine().split(" "); String[] tb = br.readLine().split(" "); String[] tc = br.readLine().split(" "); Job[] list1 = new Job[n]; Job[] list2 = new Job[n]; int n1 = 0, n2 = 0; for(int i = 0; i < n; i++) { int a = Integer.parseInt(ta[i]); int b = Integer.parseInt(tb[i]); int c = Integer.parseInt(tc[i]); if (a+b < b+c) list1[n1++] = new Job(a,b,c,i+1); else list2[n2++] = new Job(a,b,c,i+1); } Comparator <Job> c1 = new JobComparatorAB(); Comparator <Job> c2 = new JobComparatorBC(); Arrays.sort(list1, c1); Arrays.sort(list2, c2); for(int i = 0; i < n1; i++) JobExecute(list1[i].a, list1[i].b, list1[i].c); for(int i = 0; i < n2; i++) JobExecute(list2[i].a, list2[i].b, list2[i].c); int res = timeC; bw.write(res + " "); bw.newLine(); for(int i = 0; i < n1; i++) bw.write(list1[i].index + " "); for(int i = 0; i < n2; i++) bw.write(list2[i].index + " "); bw.close(); } 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,d[10001],e[10001],f[10001]; long A[10001],B[10001],C[10001]; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int i=1;i<=n;i++) scanf("%d",&e[i]); for(int i=1;i<=n;i++) scanf("%d",&f[i]); for(int i=1;i<=n;i++) { a[i]=d[i]+e[i]; b[i]=e[i]+f[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]=d[x1[1]]; B[1]=d[x1[1]]+e[x1[1]]; C[1]=d[x1[1]]+e[x1[1]]+f[x1[1]]; } else { A[1]=d[x2[1]]; B[1]=d[x2[1]]+e[x2[1]]; C[1]=d[x2[1]]+e[x2[1]]+f[x2[1]]; } for(int i=1;i<=u;i++) { A[i]=A[i-1]+d[x1[i]]; if(A[i]>B[i-1]) B[i]=A[i]+e[x1[i]]; else B[i]=B[i-1]+e[x1[i]]; if(B[i]>C[i-1]) C[i]=B[i]+f[x1[i]]; else C[i]=C[i-1]+f[x1[i]]; } for(int i=u+1;i<=u+v;i++) { A[i]=A[i-1]+d[x2[i-u]]; if(A[i]>B[i-1]) B[i]=A[i]+e[x2[i-u]]; else B[i]=B[i-1]+e[x2[i-u]]; if(B[i]>C[i-1]) C[i]=B[i]+f[x2[i-u]]; else C[i]=C[i-1]+f[x2[i-u]]; } printf("%ld\n",C[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,c,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()); st=new StringTokenizer(kb.readLine()); for(int i=0;i<n;++i) c[i].c = Integer.parseInt(st.nextToken()); for(int i=0;i<n;++i) { c[i].i=i; if(c[i].a<c[i].c) 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+x.b-y.a-y.b; if(x.t==2) return y.b+y.c-x.b-x.c; return 0; } }); int ta=0,tb=0,tc=0; for(int i=0;i<n;++i) { ta += c[i].a; if(tb<ta) tb=ta; tb += c[i].b; if(tc<tb) tc=tb; tc += c[i].c; } System.out.println((ta>tb)?(ta>tc)?ta:tc:(tb>tc)?tb:tc); for(int i=0;i<n;++i) System.out.print(c[i].i+1+" "); System.out.println(); } }
Bình luận