loj 10004

题目分析：

• 经典的带限期和罚款的单位时间任务调度问题
• 将 $w$w从大到小排序，优先处理罚款多的，将任务尽量安排在期限之前，并且靠后，如果找不到，则放在最后面

Code：

#include <bits/stdc++.h>
using namespace std;
#define maxn 510
#define re register

int n,m;
bool vis[maxn];
struct node {
	int d,w;
}e[maxn];

inline int read_() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}

inline bool cmp_(node aa,node bb) {
	//if(aa.w==bb.w) return aa.d < bb.d;
	return aa.w > bb.w;
}

void readda_() {
	m=read_();
	n=read_();
	for(re int i=1;i<=n;++i) {
		e[i].d=read_();
	}
	for(re int i=1;i<=n;++i) {
		e[i].w=read_();
	}
	sort(e+1,e+n+1,cmp_);
	memset(vis,false,sizeof(vis));
	int cnt=n;
	for(int i=1;i<=n;++i) {
		int pd=0;
		for(int j=e[i].d;j>=1;--j) {
			if(!vis[j]) {
				vis[j]=true;
				pd=1;
				break;
			}
		}
		if(!pd) {
			for( ;cnt>=1;--cnt) {
				if(!vis[cnt]) {
					vis[cnt]=true;
					m-=e[i].w;
					break;
				} 
			}
		}
	}
	printf("%d",m);
}

int main() {
	freopen("a.txt","r",stdin);
	readda_();
	return 0;
}