#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,t,k,s,a[100010],q,b[100010],tot[100010];
ll calc(ll x){
	if(x<=0)return 0;
	int p=lower_bound(a+1,a+1+n,x)-a-1;
	return x*s+k*(p*x-tot[p]);
}
ll f(ll x,ll h){
	ll ans=calc(x);
	int l=upper_bound(a+1,a+1+n,h+x)-a;
	if(l<=n)ans+=(tot[n]-tot[l-1]-(h+x)*(n-l+1))*t;
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>t>>s>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		tot[i]=tot[i-1]+a[i];
	}
	cin>>q;
	while(q--){
		ll h;
		cin>>h;
		ll l=0,r=a[n];
		while(r-l>2){
			ll mid1=(l+l+r)/3,mid2=(l+r+r)/3;
			if(f(mid1,h)<f(mid2,h))r=mid2-1;
			else l=mid1;
		} 
		ll ans=1e18;
		for(int i=l;i<=r;i++){
			ans=min(ans,f(i,h));
		}
		cout<<ans<<' ';
	}
	return 0;
}

依旧神秘导数题，会导数就很容易分析到一个抛物线状的函数（但不是严格抛物线），然后就三分。

但是你都会导数了你不会二分导数吗？

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N],d1[N],d2[N],s1[N],s2[N],n,t,s,k;
signed main()
{
	cin>>n>>t>>s>>k;
	for(int i=1;i<=n;i++)cin>>a[i],s1[0]+=a[i]*t;
	sort(a+1,a+n+1);
	int pos=0;
	for(int i=1;i<=N-10;i++)
	{
		while(pos<n&&a[pos+1]<i)pos++;
		d1[i]=-(n-pos)*t;s1[i]=s1[i-1]+d1[i];
		d2[i]=s+pos*k;s2[i]=s2[i-1]+d2[i];
	}
	int q;cin>>q;
	while(q--)
	{
		int x;cin>>x;
		int l=x,r=N-10,ans=x;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(d1[mid]+d2[mid-x]<=0)l=mid+1,ans=mid;
			else r=mid-1;
		}
		cout<<s1[ans]+s2[ans-x]<<' ';
	}
	return 0;
}

警示后人：请注意二分边界

更好的阅读体验

信息学不是数学，所以乐子题解当乐子看看就行了 /lh

思路

大胆猜测，当查询的 $h$ 变小时，用按钮的次数一定不会减少，于是上决策单调性可以直接秒掉。

接下来尝试证明一下。设允许的最高高度为 $h$，令 $f(x)$ 表示按 $x$ 次按钮的代价，$g(h,x)$ 表示按 $x$ 次后还需要单独操作的贡献以达到 $h$，则当询问 $h$ 时先按 $x$ 次按钮的代价就是 $c(h,x) = f(x) + g(h,x)$。

把 $f(x),g(h,x)$ 表示出来，其中 $cnt_i$ 表示 $a$ 中 $\leq i$ 的元素数量，$sum_i$ 表示 $a$ 中 $\geq i$ 的元素之和，$s_i$ 表示 $a$ 中 $= i$ 的元素之和，$v_i$ 表示 $a$ 中 $= i$ 的元素数量：

$$f(x) = f(x - 1) + s + k \times cnt_{x - 1}\\ g(h,x) = (sum_{h + x + 1} - (cnt_m - cnt_{h + x}) \times (x + h)) \times t$$

考虑 $c(h,x)$ 与 $c(h,x + 1)$ 的增量 $\Delta c(h,x)$：

$$\Delta c(h,x) = \Delta f(h,x) + \Delta g(h,x) = s + k \times cnt_{x - 1} + (v_{h + x + 1} - s_{h + x + 1}) \times t$$

显然 $\Delta c(h,x)$ 随 $h$ 的增大而减小，且 $c(h,x)$ 是一个单谷函数。我们希望对于每一个询问每一次选择的 $c(h,x)$ 都尽量的小，因此我们的决策点 $p$ 一定为最小的满足 $\Delta c(h,x) \geq 0$ 的数。

由于 $\Delta c(h,x)$ 单调递减，因此对于一个较大的 $h$ 其决策点 $p$ 一定较小。于是满足决策单调性的定义，证毕！

Code

#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

const int N = 2e5 + 10;
const int inf = (int)(1e18) + 10;
int n,t,s,k,q,m;
int arr[N],cnt[N],sum[N],cst[N],ans[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void dfs(int l,int r,int vl,int vr){
    if (l > r) return;
    int mid = l + r >> 1;
    int Min = inf,pos = 0;
    for (re int i = vl;i <= vr;i++){
        int val = cst[i] + (sum[mid + i + 1] - (cnt[m] - cnt[mid + i]) * (i + mid)) * t;
        if (Min > val) Min = val,pos = i;
    } ans[mid] = Min;
    dfs(l,mid - 1,pos,vr); dfs(mid + 1,r,vl,pos);
}

signed main(){
    n = read(),t = read(),s = read(),k = read();
    for (re int i = 1;i <= n;i++){
        cnt[arr[i] = read()]++; sum[arr[i]] += arr[i];
    } m = *max_element(arr + 1,arr + n + 1);
    for (re int i = 1;i <= 2 * m;i++) cnt[i] += cnt[i - 1];
    for (re int i = m;~i;i--) sum[i] += sum[i + 1];
    for (re int i = 1;i <= m;i++) cst[i] = cst[i - 1] + s + k * cnt[i - 1];
    dfs(0,m,0,m); q = read();
    while (q--) printf("%lld ",ans[read()]);
    return 0;
}