题意: 从 N 开始, 目标是把数字变成 M, 每个代理有俩个操作, 让数字减一或者变成一半, 求最小的花费
能减半就减半.
- #include <string>
- #include<iostream>
- #include<map>
- #include<memory.h>
- #include<vector>
- #include<algorithm>
- #include<queue>
- #include<vector>
- #include<stack>
- #include<math.h>
- #include<iomanip>
- #include<bitset>
- #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;
- }
来源: http://www.bubuko.com/infodetail-2919738.html