达成目标鸡蛋个数的最小操作次数

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-22 18:28:00
    编辑于：2022-03-22 21:42:07
    浏览量：567

概述

TODO

BFS

超时。

#include <bits/stdc++.h>
using namespace std;

int bfs(int x, int y) {
    queue<int> q;
    q.push(x);
    int count = 0;
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i ++) {
            int n = q.front(); q.pop();
            if (n == y) {
                return count;
            }
            q.push(n + 1);
            if (n % 3 == 0) {
                q.push(n / 3);
            }
        }
        count ++;
    }
    return -1;
}

int main() {
    int T; cin >> T;
    for (int t = 0; t < T; t ++) {
        int x, y; cin >> x >> y;
        cout << bfs(x, y) << endl;
    }
}

贪心

没能通过全部用例。

#include <bits/stdc++.h>
using namespace std;

int helper(long x, long y) {
    if (x == y) return 0;
    if (x < y) return y - x;
    int count = x % 3;
    if (count != 0) {
        count = 3 - count;
    }
    long nextX = (x + count) / 3;
    int resCount = helper(nextX, y);
    int ans = count + resCount + 1;
//    cout << "x " << x << " y " << y << " -> " << ans << endl;
    return ans;
}

int main() {
    int T; cin >> T;
    for (int t = 0; t < T; t ++) {
        long x, y; cin >> x >> y;
        int ans = helper(x, y);
        cout << ans << endl;
    }
}

Links: 达成目标鸡蛋个数的最小操作次数