P7777 『JROI-2』Shelter 题解
省流：二分求单谷函数的谷值。
前记
蒟蒻的第二篇题解。
一般的二分和
读题
首先我们仔细的研究一下这两个规则。
- 选择一个数
，把第 堆石子抓取走，代价为 。 - 选择两个数
，把第 堆和第 堆石子抓走，代价为 。
我们发现，如果我们使用第二条规则，则一定是选取相邻的两个最优；同时还发现，我们一定是在前面一部分使用规则一，后面的使用规则二，因为你编号越小，使用规则一所花费的代价就越少，如果你编号大的都使用了规则二，则编号小的也一定要使用规则二。
于是乎，我们设 后
设花费总和为
合并同类项即：
利用等差数列整理得：
我们这时可以感性理解一下，前一部分使用规则一，后一部分使用规则二，存在一个点到达最小值，那么
所以问题就转化成了求如下单谷函数的谷值。
inline int f(int i){return (n-2*i+1)*(n-2*i)/2*p+i*q;}//f(x)二分
额，一般求单峰/谷函数我们最常用的是三分法，但对于这道题来说，反正我是没有用三分法写过去，原因可能是因为本人太弱了，一些毒瘤的问题我没有想到；同时
在这道题中，是完完全全可以用二分求解单谷函数的谷值的，甚至于没有那些乱七八糟的特判，我们设一个点为
while(l<r)
{
mid=(l+r)>>1;
if(mid-1>=0&&f(mid-1)<f(mid)) r=mid-1;//如果x可以更小，并且谷值点<x
else if(mid+1<=n/2&&f(mid+1)<f(mid)) l=mid+1;//如果x可以更大，并且谷值点>x
else l=r=mid;//若不行，则x为谷值点，直接将l和r设成 mid，下一步就直接跳出了
}
printf("%lld\n",f(l));AC Code
代码挺短的，最后一个点基本可以稳定在 220ms 左右
#include<cstdio>
#define int long long
using namespace std;
int T,n,p,q;
inline int read()//快读是必要的
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline int f(int i){return (n-2*i+1)*(n-2*i)/2*p+i*q;}//f(x)
main()
{
T=read();
while(T--)
{
n=read(),p=read(),q=read();
int l=0,r=n/2,mid;//注意边界
while(l<r)
{
mid=(l+r)>>1;
if(mid-1>=0&&f(mid-1)<f(mid)) r=mid-1;//如果x可以更小，并且谷值点<x
else if(mid+1<=n/2&&f(mid+1)<f(mid)) l=mid+1;//如果x可以更大，并且谷值点>x
else l=r=mid;//若不行，则x为谷值点，直接将l和r设成 mid，下一步就直接跳出了
}
printf("%lld\n",f(l));
}
return 0;
}