Hướng dẫn giải của Lập lịch giảm thiểu trễ hạn


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 ladpro98

#include <bits/stdc++.h>

const int N = 100005;
const int INF = N;

using namespace std;

struct job {
    int index;
    int time, limit;
} a[N];
int n;

bool incTime(const job &a, const job &b) { return a.time < b.time; }
bool incLimit(const job &a, const job &b) { return a.limit < b.limit; }

struct node {
    int l, r;
    int minV, lazy;
    node *left, *right;

    node(int _l, int _r) {
        l = _l; r = _r;
        minV = INF; lazy = 0;
        left = right = NULL;
    }

    void pushDown() {
        if (l < r && left == NULL) {
            left = new node(l, l + r >> 1);
            right = new node((l + r >> 1) + 1, r);
        }
        if (lazy) {
            minV -= lazy;
            if (l < r) {
                left->lazy += lazy;
                right->lazy += lazy;
            }
            lazy = 0;
        }
    }

    void assign(int i, int v) {
        pushDown();
        if (r < i || i < l) return;
        if (l == r) {
            minV = v;
            return;
        }
        left->assign(i, v);
        right->assign(i, v);
        minV = min(left->minV, right->minV);
    }

    void decSuffix(int from, int value) {
        pushDown();
        if (r < from) return;
        if (from <= l) {
            lazy += value;
            pushDown();
            return;
        }
        left->decSuffix(from, value);
        right->decSuffix(from, value);
        minV = min(left->minV, right->minV);
    }

    int suffixMin(int from) {
        pushDown();
        if (r < from) return INF;
        if (from <= l) return minV;
        return min(left->suffixMin(from), right->suffixMin(from));
    }
};

struct T_BIT {
    int bit[N];

    T_BIT() {
        memset(bit, 0, sizeof(bit));
    }

    void update(int i, int v) {
        for (++i; i < N; i += i & -i)
            bit[i] += v;
    }

    int prefixSum(int i) {
        int ans = 0;
        for (++i; i > 0; i -= i & -i)
            ans += bit[i];
        return ans;
    }
} BIT;

int order[N];
bool was[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifdef _LAD_
    freopen("NKTARDY.txt", "r", stdin);
#endif // _LAD_
    cin >> n;
    for (int i = 0; i < n; ++i) a[i].index = i;
    for (int i = 0; i < n; ++i) cin >> a[i].time;
    for (int i = 0; i < n; ++i) cin >> a[i].limit;
    node *root = new node(0, n - 1);
    sort(a, a + n, incLimit);
    for (int i = 0; i < n; ++i) order[a[i].index] = i;
    sort(a, a + n, incTime);
    vector<job> ans;
    for (int i = 0; i < n; ++i) {
        int pos = order[a[i].index];
        int minFree = root->suffixMin(pos);
        int curTime = BIT.prefixSum(pos);
        if (curTime + a[i].time <= a[i].limit && a[i].time <= minFree) {
            ans.push_back(a[i]);
            root->decSuffix(pos, a[i].time);
            root->assign(pos, a[i].limit - curTime - a[i].time);
            BIT.update(pos, a[i].time);
        }
    }
    cout << n - ans.size() << endl;
    for (job it: ans) was[it.index] = 1;
    sort(ans.begin(), ans.end(), incLimit);
    for (int i = 0; i < n; ++i) if (!was[a[i].index]) ans.push_back(a[i]);
    for (job it: ans) cout << it.index + 1 << ' ';
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100011;
var
  f1,f2:text;
  hsize,n:longint;
  ind,dd,h,d,p:array[1..MAXN] of longint;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i:longint;
begin
  read(f1,n);
  for i:=1 to n do read(f1,p[i]);
  for i:=1 to n do read(f1,d[i]);
  for i:=1 to n do ind[i]:=i;
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
var
  mid:longint;
procedure sort(l,r:longint); inline;
var
  i,j:longint;
begin
  mid:=d[l+random(r-l+1)]; i:=l; j:=r;
  repeat
    while d[i]<mid do inc(i);
    while d[j]>mid do dec(j);
    if i<=j then
      begin
        swap(d[i],d[j]);
        swap(p[i],p[j]);
        swap(ind[i],ind[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure ans; inline;
var
  i:longint;
begin
  writeln(f2,n-hsize);
  for i:=1 to n do
    if dd[i]=1 then write(f2,ind[i],' ');
  for i:=1 to n do
    if dd[i]=0 then write(f2,ind[i],' ');
  writeln(f2);
end;
procedure downHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (p[h[j+1]]>p[h[j]]) then inc(j);
      if (p[h[j]]>p[h[i]]) then swap(h[i],h[j]);
      i:=j; j:=i<<1;
    end;
end;
procedure upHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (p[h[i]]>p[h[j]]) do
    begin
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push(u:longint); inline;
begin
  inc(hsize); h[hsize]:=u;
  upHeap(hsize);
end;
procedure pop(var u:longint); inline;
begin
  u:=h[1]; swap(h[1],h[hsize]); dec(hsize);
  downHeap(1);
end;
procedure solve;
var
  i,sum,temp:longint;
begin
  hsize:=0; sum:=0;
  for i:=1 to n do
    if sum+p[i]<=d[i] then
      begin
        sum+=p[i];
        dd[i]:=1;
        push(i);
      end
    else if (hsize>0) and (sum-p[h[1]]+p[i]<=d[i]) and (p[h[1]]>p[i]) then
      begin
        sum+=p[i]-p[h[1]];
        dd[h[1]]:=0;
        pop(temp);
        push(i); dd[i]:=1;
      end;
end;
begin
  openF;
  inp;
  sort(1,n);
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00000001
#define oo 1111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define sz(a) (int)(a.size())
#define MS(a, x) memset(a, x, sizeof(a))
//#include <conio.h>
//#define g 9.81
#define maxn 100005
double const PI=4*atan(1.0);

const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

struct Work{
    int need, finish, id1, id2;
    Work(){};
    bool operator <(Work const w)const{
        return finish < w.finish;
    }
};

Work A[100005];

struct comp{
    bool operator() (const pair<int, int> &a, const pair<int, int> &b) const{
        return A[a.fi].need > A[b.fi].need;
    }
};
multiset<pair<int, int>, comp > S;
multiset<pair<int, int>, comp >::iterator it;
int n;
int que[100005];
int size = 0, run = 0, fl[100005] = {0};
vector<int> V1, V2;

int main(){    
  //  OPEN();
    scanf("%d", &n);


    rep(i, n) scanf("%d", &A[i].need);
    rep(i, n){
        scanf("%d", &A[i].finish);
        A[i].id1 = i;
    }

    sort(A, A + n);
    rep(i, n) A[i].id2 = i;
    int t = 0, res = 0, u;

    rep(i, n){
        S.insert(MP(A[i].id2, A[i].id1));
        t += A[i].need;
        while(t > A[i].finish){
            it = S.begin();
            t -= A[(*it).fi].need;
            S.erase(it);
            fl[A[(*it).fi].id1] = 1;
        }
    }

    rep(i, n) {
        if(fl[A[i].id1]) V2.PB(A[i].id1);
        else V1.PB(A[i].id1);
    }

    printf("%d\n", n - sz(S));
    rep(i, sz(V1)) printf("%d ",V1[i] + 1);
    rep(i, sz(V2)) printf("%d ",V2[i] + 1);
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

struct rec
{
       int time,dead,lab;
};

bool cmp(rec x,rec y)
{
     return x.dead < y.dead;
};

rec a[100010];
bool b[100010];
int t[100010];
int n;

bool opt(int x,int y)
{
     return t[x] < t[y];
};

int main()
{
//    freopen("tardy.in","r",stdin);
//    freopen("tardy.ou","w",stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i].time);
    for (int i = 0; i < n; i++) scanf("%d", &a[i].dead);
    for (int i = 0; i < n; i++) a[i].lab = i;

    sort(a,a + n,cmp);
    for (int i = 0; i < n; i++) t[a[i].lab] = a[i].dead;

    priority_queue< pair<int,int> > q;
    int final_time = 0;
    for (int i = 0; i < n; i++)
    {
        q.push(make_pair(a[i].time,a[i].lab));
        final_time += a[i].time;
        while (final_time > a[i].dead)
        {
              pair<int,int> pp = q.top();  q.pop();
              final_time -= pp.first;
        };
    };

    vector<int> v;
    while (!q.empty())
    {
          pair<int,int> pp = q.top();  q.pop();  v.push_back(pp.second);
    };
    sort(v.begin(),v.end(),opt);  
    int ok = v.size();
    memset(b,true,sizeof(b));
    printf("%d\n", n - ok);
    for (int i = 0; i < ok; i++) 
    {
        printf("%d ", v[i] + 1);  b[v[i]] = false;
    };
    for (int i = 0; i < n; i++) if (b[i]) printf("%d ", i + 1);
};

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int n;
pair<pair<int,int>, int> a[100000];
priority_queue<pair<int,int> > q;
bool mark[100000];

int main() {

    scanf("%d", &n);
    for(int i=0;i<n;++i) scanf("%d", &a[i].first.second);
    for(int i=0;i<n;++i) scanf("%d", &a[i].first.first);
    for(int i=0;i<n;++i) a[i].second = i+1;
    sort( a, a+n);

    memset( mark, true, sizeof(mark));
    int total = 0;
    for(int i=0;i<n;++i) {
        total += a[i].first.second;
        q.push( make_pair( a[i].first.second, i));
        if(total>a[i].first.first) {
            pair<int,int> p = q.top(); q.pop();
            total -= p.first;
            mark[p.second] = false;
        }
    }

    int dem = 0;
    for(int i=0;i<n;++i) if(!mark[i]) ++dem;
    printf("%d\n", dem);
    for(int i=0;i<n;++i) if(mark[i]) printf("%d ", a[i].second);
    for(int i=0;i<n;++i) if(!mark[i]) printf("%d ", a[i].second);
    //system("pause");
    return 0;   
}

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.