Editorial for Lập lịch trên hai máy


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.

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=10011;
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);
    putchar(10);
    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

uses math;
var
  a,b:array[1..10111] of longint;
  n,n1,n2,i:longint;
  a1,b1,ind1,a2,b2,ind2:array[1..10111] of longint;
  ta,tb:longint;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort1(l,r:longint);
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=a1[l+random(r-l+1)];
      repeat
        while a1[i]<mid do inc(i);
        while a1[j]>mid do dec(j);
        if i<=j then
          begin
            swap(a1[i],a1[j]);
            swap(b1[i],b1[j]);
            swap(ind1[i],ind1[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort1(i,r);
      if l<j then sort1(l,j);
    end;

procedure sort2(l,r:longint);
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=b2[l+random(r-l+1)];
      repeat
        while b2[i]>mid do inc(i);
        while b2[j]<mid do dec(j);
        if i<=j then
          begin
            swap(a2[i],a2[j]);
            swap(b2[i],b2[j]);
            swap(ind2[i],ind2[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort2(i,r);
      if l<j then sort2(l,j);
    end;

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
    if a[i]<b[i] then
      begin
        inc(n1);
        a1[n1]:=a[i];
        b1[n1]:=b[i];
        ind1[n1]:=i;
      end
    else
      begin
        inc(n2);
        a2[n2]:=a[i];
        b2[n2]:=b[i];
        ind2[n2]:=i;
      end;

  sort1(1,n1);
  sort2(1,n2);

  for i:=1 to n1 do
    begin
      inc(ta,a1[i]);
      tb:=max(ta,tb)+b1[i];
    end;

  for i:=1 to n2 do
    begin
      inc(ta,a2[i]);
      tb:=max(ta,tb)+b2[i];
    end;

  writeln(tb);
  for i:=1 to n1 do
    write(ind1[i],' ');
  for i:=1 to n2 do
    write(ind2[i],' ');
end.

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();
}
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.