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

Tác giả: ll931110

Ngôn ngữ: C++

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

Download