本文共 1730 字，大约阅读时间需要 5 分钟。
题意：从N开始,目标是把数字变成M，每个代理有俩个操作,让数字减一或者变成一半,求最小的花费
能减半就减半.
#include #include #include #include #include #include #include #include #include #include #include #include #include"math.h"namespace cc{ using std::cout; using std::endl; using std::cin; using std::map; using std::vector; using std::string; using std::sort; using std::priority_queue; using std::greater; using std::vector; using std::swap; using std::stack; using std::bitset; class Input { public: char* name; int a=0; int b=0; int cost=0; Input() { name = new char[50]; }; }; constexpr int L = 110; Input ins[L]; bool cmp(Input& a, Input& b) { if (a.cost < b.cost) return true; if (a.cost > b.cost) return false; return strcmp(a.name, b.name) < 0; } void solve2(int LL, int N, int M) { for (int i = 0;i < LL;i++) { //计算花费 int h = N; while (h/2 >= M && (h - h/2) * ins[i].a >= ins[i].b) { ins[i].cost += ins[i].b; h = h / 2; } if (h > M) ins[i].cost += (h - M) * ins[i].a; } sort(ins, ins + LL, cmp); for (int i = 0;i < LL;i++) cout << ins[i].name << " " << ins[i].cost << endl; } void solve() { int cases; cin >> cases; int t = 1; while (cases--) { int N, M, LL; cin >> N >> M >> LL; for (int j = 0;j < LL;j++) { char* strs = new char[100]; cin >> strs; Input inss; sscanf(strs, "%[^:]:%d,%d", inss.name, &inss.a, &inss.b); ins[j] = inss; } cout << "Case " << t << endl; t++; solve2(LL, N, M); } }};int main(){#ifndef ONLINE_JUDGE freopen("d://1.text", "r", stdin);#endif // !ONLINE_JUDGE cc::solve(); return 0;}
转载于:https://www.cnblogs.com/shuiyonglewodezzzzz/p/10264838.html