codeforces 1244E Minimizing Difference (贪心)

蜗牛慢爬的李成广 2019-11-01

(点击此处查看原题)

题意分析

给出n个数,a1,a2...an,现在可以进行最多k次操作,每次操纵可以使得任意一个数自增或者自减,问经过最多k次操作后,n个数中的最大值-最小值最小为多少?

解题思路

一开始,看到k最大可达1e14,就知道这个肯定不能暴力求解...但是我们可以通过优化暴力的方法来解题

注意到,我们只需要考虑最大值和最小值之差,因此我们要么使得最小值增加,要么使得最大值减少,但是每个数一个个地增加太慢,所以我们记录下每个数的数量和值,这样就可以一次性将最小值或者最小值进行增减了

然后,要是我们让当前最大值和最小值仅仅自增或者自减的话,显然很浪费时间,因为会进行很多的重复操作(例:在当前最小值自增到次小值的过程中,会不断地重复同样的计算)

所以我们通过最小值min的和次小值min_s进行判断,如果当前剩余可操作次数k‘可以使得最小值增加到次小值的值,即 k‘ >= (min_s - min) * num[min],那么我们令 k‘ -= (min_s - min) * num[min],对于最大值同理

以上说明了如何快速地对数进行操作,接下来就需要考虑每次选择最大值还是最小值进行操作了

很简单的道理,选择最小值和最大值中数量num最小者进行上述所示的操作,可以用最小的操作次数使得最大者和最小值的差值最小

最后,总结算法:

【1】将n个数转化位结构体变量number,number.val表示这个数的值,number.num表示值为number.val的数的个数

【2】对number按照number.val的值升序排序

【3】每次选出number中最大值number[l] 和 最小值 numer[r]

如果number[l].num < number[r],num ,执行步骤【4】

否则,执行步骤【5】

【4】判断当前数number[l].val是否可以增加到次小值number[l+1].val

  如果 k >= (number[l+1].val - number[l].val)*number[l].num    

    k -= (number[l+1].val - number[l].val)*number[l].num;
      number[l+1].num += number[l].num;
      l++;

  否则,说明无法通过增加number[l].val 达到次小值number[l+1].val,所以让number[l].val尽量大,用尽操作次数后输出答案并结束程序

    ll left = number[l].val + k / number[l].num;
      printf("%lld\n",number[r].val - left);
      return 0;

【5】判断当前数number[r].val是否可以减少到次大值number[r-1].val

  如果 k >= (number[r].val - number[r-1].val)*number[l].num    

    k -=  (number[r].val - number[r-1].val)*number[l].num;
      number[r-1].num += number[r].num;
      r--; 

  否则,说明无法通过减少number[r].val 达到次大值number[r-1].val,所以让number[r].val尽量小,用尽操作次数后输出答案并结束程序

    ll right = number[r].val - k / number[r].num;
      printf("%lld\n",right - number[l].val);
      return 0;

【6】如果l < r ,回到步骤【3】

  否则,说明 l == r ,输出0,表示最终使得最大值和最小值相等,答案即为0

代码区

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<string>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip>

#define bug cout << "**********" << endl
#define show(x, y) cout<<"["<<x<<","<<y<<"] "
#define LOCAL = 1;
using namespace std;
typedef long long ll;
const ll inf = 1e18 + 7;
const int Max = 1e5 + 10;

struct Number
{
    ll val, num;
} number[Max];

int n, tot;
int a[Max];
ll k;

int main()
{
#ifdef LOCAL
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    sort(a + 1, a + 1 + n);
    tot = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == a[i - 1])
            number[tot].num++;
        else
            number[++tot].num = 1, number[tot].val = a[i];
    }
    int l = 1, r = tot;
    while (l < r)
    {
        if (number[l].num < number[r].num)
        {
            ll dis = (number[l+1].val - number[l].val)*number[l].num;
            if(k >= dis)
            {
                    k -= dis;
                    number[l+1].num += number[l].num;
                    l++;
            }
            else
            {
                ll left = number[l].val + k / number[l].num;
                printf("%lld\n",number[r].val - left);
                return 0;
            }
        }
        else
        {
            ll dis = (number[r].val - number[r-1].val)*number[r].num;
            if(k >= dis)
            {
                k -= dis;
                number[r-1].num += number[r].num;
                r--;
            }
            else
            {
                ll right = number[r].val - k / number[r].num;
                printf("%lld\n",right - number[l].val);
                return 0;
            }
        }
    }
    printf("0\n");
    return 0;
}

相关推荐