传送门
- 题意给出一个n个数的数组b。数组b中的n个数据表示n个数据n个数据存储于数组a的十进制表示下的数字之和并且数组a严格单调递增数组a的最后一个数据a[n]最小。请求出满足以上条件的序列a。
- 思路贪心。要使最后一位最小只要让数组a中的每一位数字尽量小即可。
- 贪心思路d b[i] - b[i - 1]。若d > 0则只需要让最低位尽可能地取9余下的作为最高位。若d 0从最低位第1位开始假设d > 0时位于第j位则让j 1 位加 1让不大于j的数位等0。若此时j 1位为9则继续将大于数位j的数字加到d上直到该数位不等于9假设为第j位然后让j 1位加 1即可。 以上过程可能不太好理解 举个例子b1 30 b2 23. d b2 - b1 -7 a1 3999第三个9是第一位也即最低位 d 9 2 > 0,第一位赋值0即3990,由于第二位和第三位都是9无法进位也不是无法进位只是进位后等于0等于就意味着d得同时加上9所以对3进位即4000此时d 2 9 9 20然后问题就转化为十进制表示下每一位数的和等于20的最小表示。
#include#include#include#include#include#include#include#include#include#include#define endl "\n"#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)#define ft first#define sd second#define pll pair#define pii pair#define ll long long int#define mt(a,b) memset(a, b, sizeof a)//#define int long longconst int inf 0x3f3f3f3f;const int INF 0x7fffffff;using namespace std;const int N 2e5 7, M 1e6;int b[400];int num[400];int net(int d, int len){int i 1;while (d > 0){while (num[i] 9) i;num[i], d--;}return max(len, i);//注意串的长度}int main(){IOS;int n; cin >> n;for (int i 1; i > b[i];int len 0;for (int i 1; i 0) len net(d, len);else{int j 1;while (d 0但是下一位是9时由于num[j]会等于 0 所以需要继续进位{d num[j];num[j] 0;}num[j]; d--;len max(j, len);//更新串的长度注意//else中此步骤以上都是为了寻找枚举的最低位转换为d > 0 的情况len net(d, len);//转换为d > 0时的情况}for (int j len; j > 1; j--)cout << num[j];cout << endl;}return 0;}
大佬链接