Codeforces Round #643 (Div. 2) E. Restorer Distance (贪心,三分)

题意:给你\(n\)个数,每次可以使某个数++,--,或使某个数--另一个++,分别消耗\(a,r,m\).求使所有数相同最少的消耗.
题解:因为答案不是单调的,所以不能二分,但不难发现,答案只有一个峰,所以我们可以三分高度,然后写个check函数贪心一下即可.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int n,a,r,m;

ll h[N];

ll check(ll x){

    ll sum=0,sum1=0,sum2=0;

      if(a+r<=m){

          for(int i=1;i<=n;++i){

              if(h[i]>x) sum+=(h[i]-x)*r;

              else if(h[i]<x) sum+=(x-h[i])*a;

          }

      }

      else{

          for(int i=1;i<=n;++i){

              if(h[i]>x) sum1+=(h[i]-x);

              else if(h[i]<x) sum2+=(x-h[i]);

          }

          ll t=min(sum1,sum2);

          sum+=t*m;

          sum+=(sum1-t)*r+(sum2-t)*a;

      }

      return sum;

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

    cin>>n>>a>>r>>m;

    for(int i=1;i<=n;++i) cin>>h[i];

    ll l=0,ri=1e9;

    while(l+20<ri){

        ll mid1=l+(ri-l)/3;

        ll mid2=ri-(ri-l)/3;

        if(check(mid1)>check(mid2)) l=mid1;

        else ri=mid2;

    }

    ll res=2e18;

    for(ll i=l;i<=ri;++i) res=min(res,(ll)check(i));

    printf("%lld\n",res);

    return 0;

}

三分模板:

因为是第一次写三分,所以这里贴一个三分模板.还是非常简单的.

    int l=0,r=1e9;

    while(l+2<r){

        int midl=l+(r-l)/3;   //左边1/3

        int midr=r-(r-l)/3;   //右边1/3

        if(check(midl)>check(midr)) l=midl;

        else r=midr;

    }

巴特西

Codeforces Round #643 (Div. 2) E. Restorer Distance (贪心,三分)

最新文章

热门文章