序列操作(divide.cpp)—CF1799B—1200
题目描述
给您一个 \(a_1,a_2,\dots a_n\) 这样的正整数数组，您可以对它进行多次（可以是零次）这样的操作：
- 选择两个索引 \(i,j(1 \leq i,j \leq n,i \neq j)\)；
- 将 \(a_i\) 赋值为 \(\lceil \frac{a_i}{a_j}\rceil\)。这里的 \(\lceil x \rceil\) 表示将 \(x\) 取值到最小的大于等于 \(x\) 的整数上。
有可能将通过这样的操作使数组的所有元素相等吗（或许为空）？如果可以，打印任何一种操作次数小于等于 \(30n\) 的操作方法。
可以证明，在问题约束下，如果存在让数组所有元素相等的操作方法，那么操作次数最多 \(30n\) 次。
输入格式
第一行仅一个正整数 \(t(1 \leq t \leq 1000)\)，表示测试数据的组数。对于测试数据的描述如下。
每一组测试数据的第一行都仅一个正整数 \(n(1 \leq n \leq 100)\)。
每一组测试数据的第二行都有 \(n\) 个正整数 \(a_1,a_2,\dots,a_n(1 \leq a_i \leq 10^9)\)。
保证所有测试数据的 \(n\) 之和不超过 \(1000\)。
输出格式
对于每一组测试数据，先输出一个整数 \(q(-1 \leq q \leq 30n)\)。如果 \(q=-1\)，表示问题无解，否则 \(q\) 表示达成目的所需的操作次数。
若 \(q \geq 0\)，则接下来的 \(q\) 行每行两个正整数 \(i,j(1\leq i,j \leq n,i\neq j)\)，表示每一次操作中的 \(i,j\)。
如果问题多解，输出其中任意一个即可。
样例 #1
样例输入 #1
10
1
100
3
1 1 1
2
2 1
2
5 5
3
4 3 2
4
3 3 4 4
2
2 100
5
5 3 6 7 8
6
3 3 80 3 8 3
4
19 40 19 55
样例输出 #1
0
0
-1
0
2
1 3
2 1
4
3 1
4 2
1 3
2 4
6
2 1
2 1
2 1
2 1
2 1
2 1
8
5 2
4 2
3 2
1 3
1 3
2 1
4 1
5 1
4
5 1
3 1
3 1
3 1
9
4 2
2 1
1 2
1 2
3 2
3 2
1 4
2 4
3 4
提示
对于前两个点，他们的每个数都已经完全相等，不需要做任何操作
对于第三个测试点，不可能将其变为相等的数
对于第五个测试点： $ [\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2] $ .
对于第六个测试点： $ [\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \to [2, 2, 2, 2] $ .
红色的是每次选择的 $ i $ ，蓝色的是每次选择的 $ j $
题解
思路
可以发现，一旦序列中出现了\(1\)，那么这个序列就无法继续被操作，所以序列中不能出现\(1\)
为了避免序列中出现\(1\)，可以每次让序列中的最小值去除以序列中的其他任意值。可以证明，如此操作下来，序列一定能被清空
证明一下：
首先，任何数无限除以\(2\)上取整，最后一定会得到\(2\)，所以只需要构造出一个\(2\)即可。
接着，我们可以发现，其实任意两个数反复进行如上的\(\lceil \frac{a_i}{a_j}\rceil\)操作时，最后的结果都会是\(2\)，所以该操作是可行的
代码
#include<bits/stdc++.h>
using namespace std;
int run()
{
int n,num1;num1=0;
pair<int,int> a[110],minn;
priority_queue<pair<int,int> >q;
vector<pair<int,int> >ans;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].first;
if(a[i].first==1) num1++;
a[i].second=i;
}
if(num1)
{
cout<<0-(num1!=n)<<endl;
return 0;
}
sort(a+1,a+n+1);minn=a[1];
for(int i=1;i<=n;i++) q.push(a[i]);
while(q.top().first!=minn.first)
{
pair<int,int> t=q.top();q.pop();
if((t.first+minn.first-1)/minn.first!=1) t.first=ceil(t.first*1.0/minn.first);
ans.push_back(make_pair(t.second,minn.second));
if(t.first<minn.first) minn=t;
q.push(t);
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++) cout<<ans[i].first<<" "<<ans[i].second<<endl;
}
int main()
{
// freopen("test.in","r",stdin);
int t;
cin>>t;
while(t--) run();
}