1483 化学变换乱搞题

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1483

首先，要知道在0---4e5内的体积下，一定存在答案。不会存在一些更大的答案。（要证明我也不晓得，我直觉）

那么我的思路就是，枚举，0--4e5，然后需要O（1）判断和更新答案。

那么预处理isok[cnt]表示产生cnt这个数字，其中有两个参数，has，表示一共有多少个数能产生这个数字。那么明显has需要等于n，才是答案的贡献。然后step，表示这n个数产生cnt这个数字，需要的步数的总和。这个可以用dfs维护。每次要么 * 2，要么 / 2，产生相同的数字，就可以return了、最优的复杂度是偶数的情况，是logn。奇数的话，也就多了几个常数，因为 / 2多次（应该不超过3次），都会变成偶数

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e5 + 20;
int mx;
struct node {
    int step;
    int has;
}isok[maxn * 4];
int vis[maxn * 4];
int DFN;
void calc(int x, int cnt) {
    if (x >= mx) return;
    if (vis[x] == DFN) return ;
    vis[x] = DFN;
    isok[x].step += cnt;
    isok[x].has++;
    calc(x * 2, cnt + 1);
    calc(x / 2, cnt + 1);
}
void work() {
    int n;
    scanf("%d", &n);
    mx = 4e5;
    for (int i = 1; i <= n; ++i) {
        int x;
        DFN++;
        scanf("%d", &x);
        calc(x, 0);
    }
    int ans = inf;
    for (int i = 0; i <= mx; ++i) {
        if (isok[i].has != n) continue;
        ans = min(ans, isok[i].step);
    }
    cout << ans << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

View Code

1483 化学变换 乱搞题

相关推荐