贪心思路,没过样例,输入2 5 2的输出6,但得了21分,求条!!!!
查看原帖
贪心思路,没过样例,输入2 5 2的输出6,但得了21分,求条!!!!
1578710
FZCmavic3pro楼主2025/7/3 20:33

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        long long x, y, k;
        cin >> x >> y >> k;
        vector<long long> a(k+1);
        for (int i = 0; i <= k; ++i) {
            cin >> a[i];
        }      
        long long diff = abs(y - x);
        if (diff == 0) {
            cout << "0\n";
            continue;
        }
        for (int i = 1; i <= k; ++i) {
            a[i] = min(a[i], 2 * a[i-1]);
        }       
        long long cost = 0, min_cost = 0;
        for (int i = k; i >= 0; --i) {
            long long power = 1LL << i;
            if (power > diff) continue;
		   	long long cnt = diff / power;        	
        	cost += cnt * a[i];
        	diff %= power;     
			for(int j = k;j >= i;j --){
	          	long long now_cost = cost;
	           	long long x_diff = diff;
				if (power > diff) continue;
	           	long long cnt = diff / power;
	        	now_cost += cnt * a[i];
	        	x_diff %= power;
	        	cost = min(cost, now_cost); 
			}
			           	
        }
        cout << cost << "\n";
    }
    return 0;
}

2025/7/3 20:33
加载中...