Codeforces-1490A Dense Array

• • 密集阵列

密集阵列

题目链接：https://codeforces.com/problemset/problem/1490/A

题目关键信息 符合密集的要求：max(a[i],a[i+1]) / min(a[i],a[i+1])≤2

题意是说相邻两个元素的最大值除以最小值不能超过2，若是超过了，就需要往里面插入数，问最少插入多少个数符合密集要求，下面来分析一个样例[4 2 10 1]

先是4和2做比较 4 / 2 = 2,符合密集的定义，继续往下走，2和10做比较，这时10 / 2 = 5,大于2，要符合插入的数最少，很明显把最小的那个值乘2再与最大值做比较可以做到插入的数最少，插入2 * 2 = 4，[4,2,4,10,1],以此类推，[4,2,4,8,10,1]->[4,2,4,8,10,2,1]->…->[4,2,4,8,10,8,4,2,1]，计算一个插了多少个数就可以了，共插入5个数。
代码如下

#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n,cnt = 0;//cnt记录一共要插入多少个数
		cin >> n;
		vector<int>a(n);
		for (int i = 0; i < n; i++)cin >> a[i];
		for (int i = 0; i < n - 1; i++) {
			if (max(a[i], a[i + 1]) > min(a[i], a[i + 1]) * 2) {
				int count = 1;//记录两个数之间要最少插入多少个数
				int Max = max(a[i], a[i + 1]), Min = min(a[i], a[i + 1]) * 2;
				while ( Min * 2 < Max)
				{
					count++;
					Min *= 2;
				}
				cnt += count;
			}
		}
		cout << cnt << endl;
	}
	return 0;
}

其实只要把题目读懂就知道怎么写了