Division

NC232422. Division

描述

给出一个正整数序列 $[a_1\dots a_n]$ 以及定值 $k$ ，每次可以选择一个区间 $[l,r]\ (r-l+1\ge k)$ ，把这个区间内的 $a_i$ 除以二下取整。是否可能通过一些操作，把所有 $a_i$ 变成 $1$ ？

若能，求出一种操作次数最少的操作方案。若有多种方案，可以输出任意一种。

输入描述

本题有多组数据。

第一行是数据组数 。

每组数据中：

第一行两个正整数 。

接下来一行  个正整数 。

同一个测试点内，所有数据中  的和不超过 。

输出描述

对于每组数据：

若无解，输出 `-1`。

若有解，第一行输出最小操作次数 。

接下来  行每行两个正整数 ，代表对  进行一次操作。

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 902ms, 内存消耗: 10804K, 提交时间: 2022-02-20 11:32:56

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
int a[N];
int l[N],r[N];
void solve()
{
	int n,k;
	cin>>n>>k;
	int cnt=0;
	memset(a,0,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		ll x;
		cin>>x;
		while(x!=1)
		x/=2,a[i]++;
	}
	for(int i=1,j;i<=n;)
	{
		if(!a[i])
		i++;
		else
		{
			for(j=i;j<=n&&a[j]>a[j-1];j++)
			a[j]--;
			if(j-i<k)
			{
				cout<<-1<<endl;
				return;
			}
			else
			{
				cnt++;
				l[cnt]=i;
				r[cnt]=j-1;
			}
		}
	}
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++)
	{
		cout<<l[i]<<" "<<r[i]<<endl;
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}