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

Tác giả: khuc_tuan

Ngôn ngữ: C++

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

Download