Codeforces Round #643 (Div. 2)(C,E补题)

C题题意:
给定 ABCD是范围,然后求xyz构成的合法三角形的个数
题解:
枚举 的值,然后可以直接算出 的范围和 的范围

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
ll ans=0;
for(int i=max(a+b,c+1);i<=b+c;i++)//2 3 6 10,此时x=2,y=3,z最小要取6,不合法
{
    int l=max(a,i-c);
    int r=min(b,i-b);//x范围
    if(l<=r)
    ans+=1ll*(r-l+1)*(min(d,i-1)-c+1);
}
cout<<ans;
}

二分针对的是单调函数，那么三分针对的是双调函数
E题题意:
给定n个高度不同的,然后要使n个变成高度相同的,然后有三个操作:
增加消耗A,删除一个消耗R,从一个上面移动到另一个上面消耗M
然后问最小消耗
题解:

然后暴力三分,三分其相等高度的值

#include<bits/stdc++.h>
using namespace std;
long long h[100009];
long long ans=1e18;
int n,a,r,m;
long long f (long long t)
{
    long long c_a=0,c_r=0;
    for(int i=0; i<n; i++)
        if(h[i]<t)
            c_a+=t-h[i];
        else
            c_r+=h[i]-t;
    long long c_m=min(c_a,c_r);
    c_a-=c_m,c_r-=c_m;
    long long   ans1=a*c_a+r*c_r+m*c_m;
    ans=min(ans,ans1);
    return ans1;
}
int main()
{

    cin>>n>>a>>r>>m;
    m=min(a+r,m);
    for(int i=0; i<n; i++)
        cin>>h[i];
    long long tl=0,tr=1e9+3;
    while(tl<tr)
    {
        long long t1=tl+(tr-tl)/3;
        long long t2=tl+(tr-tl)/3*2;
        if(f(t1)>=f(t2))
            tl=t1+1;
        else
            tr=t2-1;
    }
    cout<<ans;
}