首页 > 代码库 > Bonetrousle HackerRank 数学 + 思维题
Bonetrousle HackerRank 数学 + 思维题
https://www.hackerrank.com/contests/world-codesprint-6/challenges/bonetrousle
给定一个数n，和k个数，1--k这k个，要求选择b个数，使得这b个数的和等于n。
首先考虑最小值，在1--k中选择前b个数，是最小的，记为mi。最大值，后b个数相加，记为mx
注意到一个东西：如果mi <= n <= mx。那么是绝对可行的。因为mi总能增加1（同时保证满足要求），所以在这个区间里面的，都是可行解。
所以首先从mi开始枚举，每次把第B个数变成最大值k（第b - 1个数改成k - 1....依次类推，因为不能重复用数字）
则总能枚举到mi >= n。然后输出方案即可。
bug点：后b个数太大了，会爆LL。所以,当后面的数相加到 >= n的时候，够了，证明n是 <= mx的了，有可行解。
然后对着模拟即可。复杂度O(b)
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 1e5 + 20;LL a[maxn];void work () {// ios::sync_with_stdio(false); LL n, k, b;// scanf ("%lld%lld%lld", &n, &k, &b); cin >> n >> k >> b; //cout << n << " " << k << " " << b << endl; LL mi = 0, mx = 0; for (int i = 1; i <= b; ++i) { mi += i; } for (LL i = k; i >= k - b + 1; --i) { mx += i; //if (mx < 0) while (1); if (mx >= n) break; // ok } //cout << mi << " " << mx << endl; if (mx < n) { printf ("-1\n"); return ; } if (mi > n) { printf ("-1\n"); return ; } LL now = mi; int to = b; LL get = k; for (int i = 1; i <= b; ++i) a[i] = i; while (true) { now = now - a[to] + get; a[to] = get; if (now >= n) { LL cut = now - n; a[to] -= cut; for (int i = 1; i <= b - 1; ++i) { printf ("%lld ", a[i]); } printf ("%lld\n", a[b]); break; } to--; get--; }}int main (){#ifdef LOCAL freopen("data.txt","r",stdin);#endif int t; cin >> t;// cout << t << endl; while (t--) work (); return 0;}
Bonetrousle HackerRank 数学 + 思维题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。