Division

#include #include #include#include#includeusing namespace std;typedef long long ll;const int N = 1e5 + 10;ll b[N], c[N];int n, k;void solve() { cin >> n>> k; memset (b, 0, sizeof b); memset (c, 0, sizeof c); for (int i = 1; i<= n; i++) { ll t; cin >> t; while (t > 1) t >>= 1,b[i] ++; } for (int i = n + 1; i >= 1; i --) b[i] -= b[ i -1]; stack s; vector> ans; for (int i = 1; i <= n + k; i ++) { if (i - k >= 1) { while(b[i - k]) { s.push(i - k); b[i - k] --; } } if (b[i] < 0) { while (b[i]) { if (!s.size()) { puts("-1"); return ; } ans.push_back({s.top(), i - 1}); s.pop(); b[i] ++; } } } if (s.size()) { puts("-1"); return ; } cout << ans.size() << endl; for (auto t : ans) cout << t.first << " " << t.second << endl;} int main () { int T; cin >> T; while (T --) { solve(); } return 0;}

通过(loga[i] / log(2))转化成贪心题目. 每次选择一正一负数，a[i]--, a[j] ++; 最终整个数组为0，就成功了

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。