andyli

题解 CF1213D1&2 【Equalizing by Division】
将原序列中所有数进行处理,将当前处理的数计算所有它能变成的数以及变成那些数需要花费的最小次数,考虑如何最小化,只需...
扫描右侧二维码阅读全文
01
2019/09

题解 CF1213D1&2 【Equalizing by Division】

将原序列中所有数进行处理,将当前处理的数计算所有它能变成的数以及变成那些数需要花费的最小次数,考虑如何最小化,只需将原序列从小到大依次处理即可。
代码如下:

#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 55, maxm = 200005;

int A[maxn];  // 原序列
int cnts[maxm]; // cnts[i]表示变成所有数均变成i需要的次数
int cntc[maxm]; // cntc[i]表示变成i的数量
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]);
    sort(A + 1, A + n + 1); // 需要从小到大依次处理
    for (int i = 1; i <= n; i++) {
        int x = A[i], sum = 0;
        while (x) {
            if (cntc[x] < k) 
                cntc[x]++, cnts[x] += sum;
            // else 
            //  已经达到k个数字了,为了保证最小化次数所以不进行操作
            
            x /= 2;
            sum++;
        }
    }
    int ans = -1u / 2; // -1u/2=2^31-1
    for (int i = 1; i <= maxm; i++)
        if (cntc[i] >= k)
            ans = min(ans, cnts[i]); // 在所有满足条件的数中取出次数最小的
    printf("%d\n", ans);
    return 0;
}
Last modification:November 23rd, 2019 at 11:29 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment