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; }