CF378 D. Preparing for the Contest

题目传送门：https://codeforces.com/problemset/problem/378/D

题目大意：
有 \(n\) 个人，\(m\) 个bug，已经总资金\(s\)

第\(i\)个bug的难度为\(a_i\)，第\(i\)个人的能力值为\(b_i\)，其需要的工资为\(c_i\)

支付工资\(c_i\)后，第\(i\)个人就可以每天处理一个难度不超过\(b_i\)的bug，持续时间无限

问能否选出一些人处理这些bug？如果能，输出所需的最少天数\(d\)，以及每个bug是由谁处理的

考虑二分天数，如果需要花费\(d\)天解决问题，我们就尽可能让所有人都工作\(d\)天，至少能力越强的人，越应当工作\(d\)天

故判断天数\(d\)是否可行时，我们在剩余的bug中找到最难的一个\(k\)，选取能力值\(b_i\geqslant a_k\)中\(c_i\)最小的一个，然后除去\(d\)个bug，以此类推直到bug处理完毕

将能力值作为下标，转化为线段树维护

注：同一能力值的人有多个

/*program from Wolfycz*/
#include
#include
#include
#include
#include
#include
#include
#define Fi first
#define Se second
#define ll_inf 1e18
#define MK make_pair
#define sqr(x) ((x)*(x))
#define pii pair
#define int_inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
templateinline T frd(T x){
	int f=1; char ch=gc();
	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')    f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
templateinline T read(T x){
	int f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
inline void print(int x){
	if (x<0)	putchar('-'),x=-x;
	if (x>9)	print(x/10);
	putchar(x%10+'0');
}
const int N=1e5;
int B[N+10],C[N+10],list[(N<<1)+10],All,T;
vectorpos[(N<<1)+10],_tmp[(N<<1)+10];
struct S1{
	#define ls (p<<1)
	#define rs (p<<1|1)
	int Tree[(N<<3)+10],Temp[(N<<3)+10];
	void copy(){
		memcpy(Temp,Tree,sizeof(Tree));
		for (int i=1;i<=T;i++)	_tmp[i]=pos[i];
	}
	void paste(){
		memcpy(Tree,Temp,sizeof(Temp));
		for (int i=1;i<=T;i++)	pos[i]=_tmp[i];
	}
	void update(int p){Tree[p]=C[Tree[ls]]>1;
		Build(ls,l,mid);
		Build(rs,mid+1,r);
		update(p);
	}
	void Modify(int p,int l,int r,int x){
		if (l==r){
			pos[l].erase(pos[l].begin());
			Tree[p]=pos[l].empty()?0:pos[l].front();
			return;
		}
		int mid=(l+r)>>1;
		if (x<=mid)	Modify(ls,l,mid,x);
		if (x>mid)	Modify(rs,mid+1,r,x);
		update(p);
	}
	int Query(int p,int l,int r,int L,int R){
		if (L<=l&&r<=R)	return Tree[p];
		int mid=(l+r)>>1,Ans=0;
		if (L<=mid)	update(Ans,Query(ls,l,mid,L,R));
		if (R>mid)	update(Ans,Query(rs,mid+1,r,L,R));
		return Ans;
	}
	void print(int p,int l,int r){
		if (l==r)	return;
		int mid=(l+r)>>1;
		print(ls,l,mid);
		print(rs,mid+1,r);
	}
	#undef ls
	#undef rs
}ST;//Segment Tree
struct node{
	int Val,ID;
	node(int _Val=0,int _ID=0){Val=_Val,ID=_ID;}
	bool operator <(const node &tis)const{return ValAll)	return 0;
		ST.Modify(1,1,T,B[pos]);
	}
	return use<=All;
}
int Ans[N+10];
void solve(int x,int m){
	ST.paste();
	for (int i=1;i<=m;i+=x){
		int pos=ST.Query(1,1,T,A[i].Val,T);
		Ans[A[i].ID]=pos;
		ST.Modify(1,1,T,B[pos]);
	}
	for (int i=1;i<=m;i++)	if (!Ans[A[i].ID])	Ans[A[i].ID]=Ans[A[i-1].ID];
	printf("YES\n");
	for (int i=1;i<=m;i++)	printf("%d%c",Ans[i],i==m?'\n':' ');
}
bool cmp(int x,int y){return C[x]>1;
		if (check(mid,m))	r=mid-1;
		else	l=mid+1;
	}
	if (r==m){
		printf("NO\n");
		return 0;
	}
	solve(r+1,m);
	return 0;
}
数据结构线段树OJCodeforces其他二分答案

相关

标签