Hướng dẫn giải của Lập lịch trên hai 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.

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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.