链接:https://ac.nowcoder.com/acm/contest/11185/C
来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
给出一个正整数序列 [a_1dots a_n][a
1
…a
n
] 以及定值 kk,每次可以选择一个区间 [l,r] (r-l+1ge k)[l,r] (r−l+1≥k),把这个区间内的 a_ia
i
除以二下取整。是否可能通过一些 *** 作,把所有 a_ia
i
变成 11?
若能,求出一种 *** 作次数最少的 *** 作方案。若有多种方案,可以输出任意一种。
输入描述:
本题有多组数据。
第一行是数据组数 TT。(1le Tle 2000)(1≤T≤2000)
每组数据中:
第一行两个正整数 n,kn,k。(1le kle nle 10^4)(1≤k≤n≤10
4
)
接下来一行 nn 个正整数 a_1sim a_na
1
∼a
n
。(1le a_ile 10^{15})(1≤a
i
≤10
15
)
同一个测试点内,所有数据中 nn 的和不超过 2times 10^42×10
4
。
输出描述:
对于每组数据:
若无解,输出 -1。
若有解,第一行输出最小 *** 作次数 mm。
接下来 mm 行每行两个正整数 l,rl,r,代表对 [l,r][l,r] 进行一次 *** 作。(1le lle rle n)(1≤l≤r≤n)
示例1
输入
复制
2
5 3
3 3 5 3 3
5 3
3 3 3 5 3
输出
复制
2
1 3
3 5
-1
思路 :
首先将原数组转化一下,问题就转化为将新的数组中每个元素值都变为0为了使 *** 作次数最少,对于每一个左端点,枚举贪心最优的右端点,选一个尽可能大的 非递减 的区间,然后将它们值都减一,作为一次 *** 作
#include#include using namespace std; typedef long long ll; const int N = 1e4 + 10, M = 1e6 + 10; int a[N]; int ansl[M], ansr[M], cnt; void solve() { int n, k; cin >> n >> k; // memset(a, 0, sizeof a); for (int i = 1; i <= n; i ++ ) { ll x; cin >> x; a[i] = 0; while (x > 1) x >>= 1, a[i] ++ ; } int l, r; cnt = 0; for (l = 1; l <= n; ) { if (!a[l]) l ++ ; else { for (r = l; r <= n && a[r] >= a[r - 1]; r ++ ); if (r - 1 - l + 1 < k) { cout << -1 << endl; return ; } for (int i = l; i <= r - 1; i ++ ) a[i] -- ; ansl[ ++ cnt] = l, ansr[cnt] = r - 1; } } cout << cnt << endl; for (int i = 1; i <= cnt; i ++ ) cout << ansl[i] << ' ' << ansr[i] << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int _; cin >> _; while (_ -- ) solve(); }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)