洛谷P 3745[六省合同試験2017]期末試験(bzoj P 4868[Shoi 2017]期末試験)

トランスファゲート
素晴らしいですね.最初は欲張りばかり考えていました.問題解を見てやっと3点が分かった.
学生一人一人が自分のすべてのランキングを知っていなければならないので、終了時間が固定されている限り、o(n)は必要な価値を算出することができ、この関数を見ると、先生の満足度は単調に上昇する曲線である.学生は下がる.そのゲートは2本の線を合成してきっと1本の二次関数のそして0から正の無限の単峰の曲線(凸の関数)に属して、そこで3分の終わりの時間はできます
注意:この問題に穴があいているところcが1 e 16に等しい可能性があるので、学生を不満にさせることはできないに違いないので、終了時間を最小にすればいいです.奥さん、またlong long!!
コード:

#include
#include
#define ll  long long
using namespace std;
const ll oo=9223372036854775807ll;
const int Maxn=200005;
ll a,b,c,n,m,l=oo,r=0;
ll t[Maxn],gb[Maxn];
ll c1(ll x)
{
	ll l=0,r=0;
	for(ll i=1;i<=m;i++)
		if(gb[i]>=x)l+=gb[i]-x;
		else r+=x-gb[i];
	if(b>a)
	{
		if(r>=l)return l*a;
		else return r*a+(l-r)*b;
	}
	return l*b;
}
ll c2(ll x)
{
	ll sum=0;
	for(ll i=1;i<=n;i++)		
		if(t[i]=1e16)
	{
		printf("%lld",c1(l));
		return 0;
	}
	while(r-l>5)
	{
		ll lm=(r-l)/3+l,rm=r-(r-l)/3;
		if(c1(lm)+c2(lm)>c1(rm)+c2(rm))
			l=lm;
		else
			r=rm;
	}
	ll ans=oo;
	for(ll i=l+1;i<=r;i++)
		ans=min(ans,c1(i)+c2(i));
	printf("%lld",ans);
	return 0;
}