程序员进阶之算法练习（五十一）
正文
题目1
题目链接 题目大意： 给出一个图形，下面是n=1、2、3、4的时候：
现在需要把上面的图形染色，由若干个菱形组成； 问，有多少种染色方法？
输入： 第一行，整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行，整数? (1≤?≤10^9).
输出： 每个样例一行，染色的方法数量。
Examples input 2 2 1 output 2 1 样例解释： 对于样例1，当n=2的时候一共有2种染色方法：
对于样例2，当n=1的时候，只有1种染色方法：
题目解析： 找规律的问题，先从n=1开始考虑，只有一种方案； n=2的时候，我们可以采用染色方案1，将第一个竖着的菱形染色；也可以先上下斜着放，将第二个竖着的菱形染色； 同理n=3时，有将第1、2、3个菱形染色的方案； 总结规律， ans=n；
代码实现：
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << n << endl;
}
return 0;
}题目2
题目链接 题目大意： 有n个砝码，每个砝码的重量是一样的； 由于砝码的重量标识已经模糊，只能大概知道的重量区间是在 [a-b, a+b]这个区间内； 现在想知道，这n个砝码的重量，能否在区间[c-d, c+d]内； 如果可以，则输出YES；如果不可以，则输出NO；
输入： 第一行，整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行，5个整数 n,?,?,?,? (1≤?≤1000, 0≤?<?≤1000, 0≤?<?≤1000)
输出： 每个样例一行，如果可以，则输出YES；如果不可以，则输出NO；
Examples input 5 7 20 3 101 18 11 11 10 234 2 8 9 7 250 122 19 41 21 321 10 3 10 8 6 1
output Yes No Yes No Yes
题目解析： 因为a和b比较小，枚举下a和b的区间，可以解决问题；
但是假如，a和b很大呢？（0≤?<?≤10^9, 0≤?<?≤10^9） 我们用[l, r]来表示[c-d, c+d]的区间； 我们用[gapL, gapR] 来表示[(a-b)n, (a+b)n]的区间； 只要这俩个区间有重叠，则表示存在可能性； 这样就不用枚举，复杂度从O(N^2)变成O(1)。
代码实现：
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
lld n, a, b, c, d;
cin >> n >> a >> b >> c >> d;
lld l = (c - d), r = (c + d);
lld ans = -1;
lld gapL = (a - b) * n, gapR = (a + b) * n;
bool ok = 0;;
if (gapL <= l && l <= gapR) {
ok = 1;
}
else if (gapL <= r && r <= gapR) {
ok = 1;
}
else if (l <= gapL && gapL <= r) {
ok = 1;
}
else if (l <= gapR && gapR <= r) {
ok = 1;
}
if (ok) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
}题目3
题目链接 题目大意： 有n个整数组成的数组，现在对数组的元素重新组织，希望新的数组满足： |?[1]−?[2]| ≤ |?[2]−?[3]| ≤ … ≤ |?[?−1]−?[?]| 求新的数组。
输入： 第一行，整数?表示有t个样例数量 (1≤?≤1000) 接下来每t个样例，第一行， 整数? (3≤?≤10^5) 第二行是n个整数，?1,?2,…,?? (−10^9≤??≤10^9).
输出： 每个样例一行，新数组的n个整数；
Examples input 2 6 5 -2 4 8 6 5 4 8 1 4 2 output 5 5 4 6 8 -2 1 2 4 8
题目解析： 假设n个数字散落在一维数轴上，那么任意两个数字的绝对值之差，就是两个数字在数轴之间的间距； 题目的问题转化为，求一个排列，使得相邻两个数字的间距越来越大； 假设从小到大排序完之后，数组是a[N]；容易知道，所有数字中间距的是a[n]-a[1]，那么可以将这个数字放到最右边； 同理，第二大的数字要么是a[1]和a[n-1]，要么是a[2]和a[n]，我们任取其中一种，假设是a[1]和a[n-1]； 同理，第三大的数字就是a[2]和a[n-1]； 同理，第四大的数字就是a[3]和a[n-1]； 如此交替选择，会使得间距越来越小，得到了一种满足题意的解法；
代码实现：
int a[N];
int ans[N];
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >>a[i];
sort(a, a + n);
int l = 0, r = n - 1, k = n - 1;
while (l <= r) {
ans[k--] = a[r--];
if (l <= r) {
ans[k--] = a[l++];
}
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
return 0;
}题目4
题目链接 题目大意： n个数字的数组，如果某个数字比相邻左右两个数字大，则称为峰；
从n个数字里面选出连续的k个数字，希望包括尽可能多的山峰； 如果有多种可能，使得第一个位置尽可能小；
输入： 第一行，整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例第一行，整数n和k (3≤?≤?≤2⋅1e5) 第二行n个整数, ?1,?2,…,?? (0≤??≤1e9, ?? ≠ ?[?+1])
输出： 每个样例一行，输出整数t和l，分别表示k个连续数字最多能被峰分为几部分，以及区间开始位置；
Examples input 2 8 6 1 2 4 1 2 4 1 2 5 3 3 2 3 2 1
output 3 2 2 2
样例解释： 样例一选择的数字区间是[2, 7]，峰的数字有4和4，可以把区间分为3部分，区间开始位置是2； 样例二的区间是[2, 4]，峰的数字只有3，可以把区间氛围2部分，区间开始位置是2； 题目解析： 先找出所有的山峰，假设是m个，遍历这些山峰； 对于第1个山峰，直接放入队列q； 对于第2个山峰，直接放入队列q，接下来判断队列中的距离是否超过k：如果满足q.back() - q.front() + 2 >= k 则表示队列中山峰已经无法用连续的k个数字来包括； 此时需要pop掉队头的山峰，也是最早加入的数字。
每加入一个数字到山峰，检查完队列数字的合法性，接着计算这个队列的结果是否更优；
代码实现：
int a[N];
queue<int> q;
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
while (!q.empty()) {
q.pop();
}
int ans = 0, start = 0;
for (int i = 1; i < n - 1; ++i) {
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
q.push(i);
while (q.back() - q.front() + 2 >= k) {
q.pop();
}
if (q.size() > ans) {
ans = q.size();
start = q.back() + 1 - (k - 1);
}
}
}
cout << ans + 1 << " " << max(0, start) + 1 << endl;
}
return 0;
}题目5
题目链接 题目大意： 给出n个整数的数组，现在每秒可以对数组进行一次操作： 第x秒，可以从数组中选择出来若干个数，将每个数加上2^(x-1）；
现在希望数组满足?1≤?2≤…≤?? ，问最少需要多少秒；
输入： 第一行，整数?表示有t个样例数量 (1≤?≤1000) 接下来t个样例，第一行，整数? (1≤?≤10^5) 第二行，n个整数 ?1,?2,…,?? (−109≤??≤109).
输出： 最少需要秒数；
Examples input 3 4 1 7 6 5 5 1 2 3 4 5 2 0 -4 output 2 0 3
题目解析： 按照题意，分别可以加上数字1、2、4、8、16、、、 由于数字递增很快（指数级），可以遇见不会添加很多次； 那么可以考虑暴力来解决，枚举x=0、1、2、3、4、5、6的情况是否满足要求，每次枚举的复杂度是O（NLogM）；M是数字大小，最多枚举LogM次；
接着，需要找一种能快速验证，当x=k的时候，是否满足要求； 由贪心的思想，我们知道对于数字a[n]，由于预期a[n]是最大的数字，可以直接将所有的数字加到a[n]上； 对于数字a[n-1]，我们希望a[n-1]在满足a[n-1]<=a[n]的情况下，尽可能的大； 同理，我们希望a[n-2]、a[n-3]、、、都是如此的处理；
那么问题变成，如何保证a[i-1]在满足a[i-1]<=a[i]的情况下，a[i-1]尽可能的大？ 答案就是：从大到小的加数字(2^(x-1))，直到数字无法添加，此时数字就是最大；
注意，这里不是从小到大；比如说数字6变成12，如果从大到小有6+4+2=12，但是如果变成从小开始，则会出现取了数字1、2之后，无法取4，最大值就是9；
代码实现：
typedef long long lld;
lld p[N];
lld a[N];
bool check(int n, int k) {
lld last = llinf;
for (int i = n - 1; i >= 0; --i) {
lld tmp = a[i];
for (int j = k; j >= 1; --j) {
if (tmp + p[j-1] <= last) {
tmp += p[j - 1];
}
}
if (tmp > last) {
return false;
}
last = tmp;
}
return true;
}
int main(int argc, const char * argv[]) {
// insert code here...
p[0] = 1;
for (int i = 1; i < 31; ++i) p[i] = p[i-1] * 2;
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
int k = 0;
while (1) {
if (check(n, k)) {
cout << k << endl;
break;
}
k++;
}
}
return 0;
}总结
题目1是找规律，注意看样例； 题目2是区间重叠，其实是判断两个区间是否存在重叠； 题目3是构造，需要一点点想法，借住数轴更容易想通； 题目4是贪心，尽量保证最长的一个队列，然后枚举每一个位置； 题目5是暴力+贪心，发现题目计算次数不多，寻找一个快速验证的方法。