NKTARDY - Lập lịch giảm thiểu trễ hạn

Tác giả: hieult

Ngôn ngữ: C++

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

Download