b2bchain区块链学习技术社区本文介绍了程序员进阶之算法练习（五十一）求职学习资料，有助于帮助完成毕业设计以及求职，是一篇很好的资料。
对技术面试,学习经验等有一些体会，在此分享。
正文
题目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) {正文
题目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) {正文
题目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) {部分转自互联网，侵权删除联系
最新评论