本文主要是介绍think-cell Round 1 (A~C),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
think-cell Round 1
目录:A B C
A题:Maximise The Score
标签: 贪心(greedy)排序(sortings)
题目大意
- 有一个长度为 2n,数值为 1 − 1e7 的数组a,可执行如下操作:
- 每步在a中选择两个数x, y删除,分数增加min(x, y)
- 问:以最佳方式走完 n 步,计算最终能得到的最高分。
思路
- 将a数组从大到小排序,每次加分为两数的最小值,易看出数组a中最大值一定不会作为分数加入,最大值与任意数一起删除可以将任意数作为分数加入,贪心的选择第二大的值与最大值一起被删除,重复此操作即为最优
AC代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{int n; cin >> n;vector<int> a(2 * n);for (int i = 0; i < 2 * n; i++)cin >> a[i];sort(a.begin(), a.end());int res = 0;for (int i = 0; i < n; i++) res += a[2 * i];cout << res << endl;
}
int main()
{int T; cin >> T;while(T--)solve();return 0;
}
B题:Permutation Printing
标签: 构造(constructive algorithms)数学(math)
题目大意
- 构造一个长度为n的数组满足:不存在两个不同的索引 i 和 j ( 1 ≤ i , j < n;i ≠ j),使得 pi整除 pj 和 pi+1 整除 pj+1。
思路
- 任意> n 2 \frac{n}{2} 2n的数字都不可能是任何数字的倍数, 所以我们只要把> n 2 \frac{n}{2} 2n和其他数字交替放即可
AC代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{int n; cin >> n;int l = 1, r = n;for (int i = 1; i <= n; i++) {int x;if (i % 2) x = l++;else x = r--;cout << x << " \n"[i == n];}
}
int main()
{int T; cin >> T;while(T--)solve();return 0;
}
C题:Lexicographically Largest
标签: 构造(constructive algorithms)数据结构(data structures)贪心(greedy)排序(sortings)
题目大意
- 有一个长度为 n 的数组 a 和一个集合 S (S中不含重复数字),进行以下三步操作恰好 n 次
- 选择一个索引 i ,使得 1 ≤ i ≤ n
- 将 ai + i 插入 S
- 删除ai。注意: ai 右边所有元素的索引将减少1 。
- 最后将集合S中数字从大到小排序,找到字典序最大的一个排序后的集合
思路
- 因为最后会进行排序,集合中的数越大越好,先选择前面的数后面索引 i会减小,所以先选后面的数字插入集合最优
- 考虑:集合要去重,如果数组q是数组p的前缀且 p≠q 那么p的字典序大于q。所以需要将相同的数字减少去重达到增大数组长度的目的
- 也就是如果存在相同的数字那么就先取其前面的数,使其索引减少,如此最终集合的长度一定可以取到n
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int a[N];
void solve()
{int n; cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];a[i] += i;}sort(a + 1, a + 1 + n, greater());for (int i = 2; i <= n; i++) {a[i] = min(a[i], a[i-1] - 1);}for (int i = 1; i <= n; i++) {cout << a[i] << " \n"[i == n];}
}
int main()
{int T; cin >> T;while(T--)solve();return 0;
}
logo
//へ /|
// /\7 ∠_/
// / │ / /
// │ Z _,< / /`ヽ
// │ ヽ / 〉
// Y ` / /
// イ● 、 ● ⊂⊃〈 /
// () へ | \〈
// >ー 、_ ィ │ //
// / へ / ノ<| \\
// ヽ_ノ (_/ │//
// 7 |/
//
/*__ _,--="=--,_ __/ \." .-. "./ \/ ,/ _ : : _ \/` \\ `| /o\ :_: /o\ |\__/`-'| :="~` _ `~"=: |\` (_) `/.-"-. \ | / .-"-.
.---{ }--| /,.-'-.,\ |--{ }---.) (_)_)_) \_/`~-===-~`\_/ (_(_(_) (
( )) (
'---------------------------------------'
*/
这篇关于think-cell Round 1 (A~C)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!