【三分整理】整数三分and浮点数三分

【浮点数三分】洛谷：P3382 三分模板

www.luogu.com.cn/problem/P3382

前置知识：三分-->用来计算凸/凹函数，即单峰/谷函数的极值点分为整数三分和浮点数三分俩种，其中整数三分的题目更加变化多端

对于浮点数三分，我们只需要设置mid左右俩边相等距离的俩个值midl和midr分别计算答案比较即可。如果cal(midl)>cal(midr)) ，那么舍弃右区间，r=midr，否则舍弃左区间，l=midl，具体实现可以参考如下代码，记住可以使用秦九韶算法加速计算多项式过程

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define eps 1e-6
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e6+5;
const ll mod=1e9+7;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}

int n;
double equiton[20];

/*double cal(double x){
    double res=0,tmp;
    per(i,n,0){
        tmp=1;
        rep(j,1,i){
            tmp*=x;
        }
        res+=equiton[i]*tmp;
    }
    return res;
}*/
double cal(double x){//秦九韶算法算多项式
    double sum=0;
    for(int i=n;i>=0;i--)
        sum=sum*x+equiton[i];
    return sum;
}
 

int main()
{
    n=read();
    double l,r;
    scanf("%lf %lf",&l,&r);
    per(i,n,0) scanf("%lf",&equiton[i]);
    double ans=0;
    while(fabs(l-r)>=eps)
    {
        double mid=(l+r)/2;
        if(cal(mid+eps)>cal(mid-eps)) l=mid;//舍弃左区间
        else r=mid;
        /*
		double mid=(l+r)/2;
        double rmid=(mid+r)/2;
        if(cal(mid)>cal(rmid)) r=rmid;
        else  l=mid;
		*/ 
    }
    printf("%lf",r);
}

【整数三分】

1.CF1355E Restorer Distance

2.2021ICPC济南 D Arithmetic Sequence

https://www.luogu.com.cn/problem/CF1355E https://pintia.cn/problem-sets/1459829212832296960/problems/1459829264400629763

对于题一的题意：

你要修理一堵墙，这堵墙由 N 个宽度为一的砖块构成，其中第 i 块砖的高度为 hi 。

你需要执行下列操作让这 NN 块砖的高度变得全部相等。

1、使一块砖的高度加一，这需要花费 A 的代价。

2、使一块高度为正的砖的高度减一，这需要花费 R 的代价。

3、使一块高度为正的砖的高度减一，另一块砖的高度加一，这需要花费MM 的代价。

给定 N,A,R,M,你需要求出使所有砖的高度变得相同的最小代价。

首先我们可以发现，对于第三种移动的操作，就相当于一增一减，那么我们可以让M=min(M,A+R)。

假设我们想要的答案高度为H，那么我们可以设

X= $\sum_{hi<H}(H-hi)$

Y= $\sum_{hi>H}(hi-H)$

如果X>Y,那么我们可以设代价为C，由于X>Y，那么我们可以先把Y多的的那部分用第三种操作移到少的部分中，剩下的再用第一种方式凑齐

即C=MY+A(X-Y)

同理可以得到假如X<Y , C=MX+R(Y-X)

对于整数三分的题，我们往往会使用变化量这种形式来证明其凹凸性，但是其实由于可以使用打表观察来猜测答案，由于如果要使用三分，那么其函数一定是单峰或者单谷的，所以往往都是打表观察后直接莽。

因为往往证明的过程都很繁琐，比如这题，具体的证明过程参考洛谷上聚聚的证明。 (自己折腾了俩小时看了好多篇题解才算是入了门)

https://www.luogu.com.cn/blog/wsyhb/post-ti-xie-cf1355e-restorer-distance

打表观察后猜测对于代价C随着H的变化，是先增后减的下凸函数，有唯一最小值，那么直接莽整数三分求极值点的代价

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e5+5;
const ll mod=1e9+7;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}

ll a[maxn],pre[maxn];
ll n,A,R,M;

ll cal(ll h)
{
    ll pos= upper_bound(a+1,a+1+n,h)-a-1;
    ll X=pos*h-pre[pos],Y=(pre[n]-pre[pos])-(n-pos)*h;
    if(X>Y) return M*Y+A*(X-Y);
    return M*X+R*(Y-X);
}

int main()
{
    n=read(),A=read(),R=read(),M=read();
    M=min(M,A+R);//移动的过程就相当于一增一减
    rep(i,1,n) a[i]=read();
    sort(a+1,a+1+n);
    rep(i,1,n) pre[i]=pre[i-1]+a[i];
    ll l=a[1],r=a[n];
    //通过严谨的证明可以得出这是一个单谷函数，先减后增，使用整数三分。
    //遇到类似的题时，可以通过假设答案，然后分析答案+1有什么变化，然后就可以求出导数
    //然后分类讨论情况，往往就是一个单谷/峰函数
    while(l<r)
    {
        ll midl=l+(r-l)/3,midr=r-(r-l)/3;
        if(cal(midl)<cal(midr)) r=midr-1;
        else l=midl+1;
    }
    printf("%lld\n",cal(l));
}

题二：等差数列

(由于之前没有写过关于整数三分的题目，让自己在济南站打了铁，悔恨莫及)

题意就是给你n个数，要求拟合成一个等差数列，每个数变化1就要消耗1的代价，求代价和最小

由于我们不知道d是多少，那么我们可以三分d，怎么三分呢。

由等差数列的知识我们知道

$a_{n} = a_{1} + (n - 1) d$

设对于n个数中的每一个数，我们都可以求出来其首项

$c_{1} = a_{i} - (i - 1) d$

接下来问题就转化成了选取哪一个首项可以使得这n个数距离首项的距离和最小。这是一个经典的货仓选址问题，原问题是这样的:

在一条数轴上有 N 家商店，它们的坐标分别为 $A_{1}, A_{2} . . . . A_{n}$

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

贪心的结果是选取其中位数，对于此题也一样，我们在n个首项排完序后选其中位数即可。使用C++内置的nth_element函数可以在O(n)的时间内求出其中位数。那么代价的计算到这里就结束了。

为什么和三分有关系呢，这就又是玄学了。我们可以很肯定的是，当我们的首项特别特别小或者特别特别大的时候，代价和肯定是很大的，那么我们可以猜测代价和关于公差d是不是一个单谷函数，有唯一的d对应其代价和最小。打表发现确实满足此规律，因此猜测完这是一个单谷函数后就可以直接使用三分冲冲冲。

具体的证明过程可以使用拉格朗日插值，but我不太会，猜就完事儿了

要注意的是等差数列可以是递增也可以是递减，还有这题会爆ll，直接开int128就行了

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e6+5;
const ll mod=1e9+7;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}

__int128 Min(__int128 x,__int128 y)
{
    return x>y?y:x;
}

__int128 Abs(__int128 x)
{
    return x>0?x:-x;
}

__int128 a[maxn],c[maxn];

int n;

__int128 cal(ll d)
{
    __int128 res=0;
    rep(i,1,n) c[i]=a[i]-(i-1)*d;
    nth_element(c+1,c+1+n/2,c+n+1);
    __int128 tmp=c[1+n/2];
    rep(i,1,n)
    {
        res+=Abs(a[i]-tmp);
        tmp+=d;
    }
    return res;
}

void print(__int128 x)
{
    if(x>9) print(x/10);
    putchar('0'+x%10);
}

int main()
{
    n=read();
    rep(i,1,n) a[i]=read();
    ll l=-1e13,r=1e13;
    __int128 ans=0;
    while(l<r)
    {
        ll midl=l+(r-l)/3,midr=r-(r-l)/3;
        __int128 x=cal(midl),y=cal(midr);
        ans=Min(x,y);
        if(x>y) l=midl+1;
        else r=midr-1;
    }
    print(ans);
}