CodeForces 377B 優先隊列 + 二分

CodeForces 377B 優先隊列 + 二分

題目：

呵呵，這破題目搞了我兩個小時，首先題意就有點怕怕的，n個人，具有解決bug的能力，一天只能解決一個，m個bug，bug具有一個難度，只有某個人能力大於等於這個難度才可以解決，請n個人解決一個問題，每個人都要拿鈔票的，問不超過s元 的情況下 最快的解決辦法

輸出每個bug由哪個人解決的方案

先考慮了DP，發現不行，後來就覺得是貪心了，那麼就跟優先隊列聯系上了，把bug的難度 跟人的 解決辦法能力都從大到小排，然後開始二分枚舉解決天數，假設解決天數為t，那麼最厲害的那個人且花費比較合適的那個人最多使用t次，都從大到小排，然後再優先隊列一下能解決問題的花費最少的人，每一次更新，若他能解決第一個問題，那麼接下裡的 t-1個問題他都可以解決，更新是從前往後更新的，所以肯定是最優的，中間花費超過s的方案可以捨去，沒辦法解決當前未解決的最大難度的bug也要捨去，二分枚舉的 最後一個能成功的肯定就是最優的了，

一開始 看看是否最難的bug有人能夠解決，否則 輸出No

還要看看m天是否有解決方案，因為最多是使用m天，若無法解決那麼輸出no

接下來才枚舉天數

一開始沒相當去枚舉解決時間，結果弄得很麻煩，後來想到了，敲了，結果中途優先隊列有個地方手賤敲錯了，一直在調試解決函數，真是醉了。。

int n,m,s;

typedef struct Node {
	int id;
	int nnum;
	bool operator<(const Node &aa)const {
		return nnum > aa.nnum;
	}
};

Node bug[100000 + 55];

typedef struct NODE {
	int id;
	int ablity;
	int cost;
	bool operator<(const NODE & aa)const {
		return cost > aa.cost;
	}
};

NODE stu[100000 + 55];

int maxn;

int ans[100000 + 55],tmp[100000 + 55];

void init() {
	memset(bug,0,sizeof(bug));
	memset(stu,0,sizeof(stu));
}

bool input() {
	while(cin>>n>>m>>s) {
		maxn = -1;
		for(int i=0;i>bug[i].nnum;
			bug[i].id = i + 1;
			maxn = max(maxn,bug[i].nnum);
		}
		for(int i=0;i>stu[i].ablity;
			stu[i].id = i + 1;
		}
		for(int i=0;i>stu[i].cost;
		return false;
	}
	return true;
}

bool cmp(NODE x,NODE y) {
	return x.ablity > y.ablity;
}

bool isok(int t) {
	int ret = 0;
	priority_queue q;
	for(int i=0,j=0;i= bug[i].nnum)q.push(stu[j]);
			else break;
		}
		if(q.size() == 0)return false;
		NODE qq = q.top();
		q.pop();
		ret += qq.cost;
		if(ret > s)return false;
		int mark = 0;
		for(int j=i;j= maxn && stu[i].cost <= s)flag = true;
	}
	if(!flag) {puts("NO");return;}
	sort(bug,bug + m);
	sort(stu,stu + n,cmp);
	int cc = 0;
	if(!isok(m)){puts("NO");return ;}
	int l = 1,r = m;
	while(l <= r) {
		int mid = (l + r)>>1;
		if(isok(mid))r = mid - 1;
		else l = mid + 1;
	}
	puts("YES");
	for(int i=1;i<=m;i++)
		printf("%d%c",ans[i],i == m?'\n':' ');
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}