【2019.8.15 慈溪模拟赛 T1】插头（plugin）（二分+贪心）

二分

首先，可以发现，最后的答案显然满足可二分性，因此我们可以二分答案。

然后，我们只要贪心，就可以验证了。

贪心

不难发现，肯定会优先选择能提供更多插座的排插，且在确定充电器个数的情况下，肯定选择能经过排插数量最大的那些充电器。

所以，我们只要模拟插排插的过程，记录当前深度\(d\)、插座数\(t\)即可。

设选择的能经过排插数量恰好为\(d\)的充电器有\(x\)个，则若\(t<x\)，显然不合法。

否则，我们将\(x\)个位置插上充电器，其余位置尽可能地插排插，就可以了。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 400000

#define LL long long

#define Gmax(x,y) (x<(y)&&(x=(y)))

using namespace std;

int n,m,a[N+5],b[N+5];

class FastIO

{

	private:

		#define FS 100000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		char c,*A,*B,FI[FS];

	public:

		I FastIO() {A=B=FI;}

		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}

}F;

class GreedySolver

{

	private:

		I bool Check(CI x)

		{

			RI i,p=1,q=x,d=0;LL t=1,nt;W(q)

			{

				W(q&&d==b[q]) --t,--q;if(t<0) return false;//插充电器

				for(i=t;i&&p<=n;--i) t+=a[p++]-1;++d;//插排插

			}return true;

		}

	public:

		I void Solve()

		{

			W(a[n]<=1) --n;RI l=1,r=m,mid;//删去无用的排插

			W(l<r) Check(mid=l+r+1>>1)?l=mid:r=mid-1;printf("%d",l);//二分答案

		}

}G;

I bool cmp(CI x,CI y) {return x>y;}

int main()

{

	freopen("plugin.in","r",stdin),freopen("plugin.out","w",stdout);

	RI i;for(F.read(n),F.read(m),i=1;i<=n;++i) F.read(a[i]);for(i=1;i<=m;++i) F.read(b[i]);//读入

	return sort(a+1,a+n+1,cmp),sort(b+1,b+m+1,cmp),G.Solve(),0;//排序，贪心

}

巴特西

【2019.8.15 慈溪模拟赛 T1】插头（plugin）（二分+贪心）

二分

贪心

代码

最新文章

热门文章