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