Editorial for Lập lịch trên 2 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=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();
    }
}

Comments

Please read the guidelines before commenting.


  • -1
    chrisson  commented on Oct. 1, 2024, 2:37 a.m.

    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;

        vector&lt;pair<int, int>> a;
    vector&lt;pair<int, int>> b;

    for(int i = 0; i < n; i++) 
    {
        int ai, bi;
        cin >> ai >> bi;
        if(ai <= bi) a.push_back({ai, bi});
        else b.push_back({ai, bi});
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), cmp);


    vector&lt;pair<int, int>> schedule = a;
    for(auto &p : b) schedule.push_back(p);

    int total_time = 0;
    int time_a = 0, time_b = 0;

    for(auto &job : schedule) {
        time_a += job.first;
        time_b = max(time_b, time_a) + job.second;
    }

    total_time = time_b;

    cout << total_time << endl;

    return 0;

    }