正文
题目1
题目链接
题目大意：
有一个由数字0、1组成的字符串，长度为n；
现在需要将其切分成若干段，要求每一段0和1的数量是不相同的。
比如说1, 101, 0000是不一样的，01, 1001, 111000是相同的。
问最少需要分成几段？
输入：
第一行，𝑛 (1≤𝑛≤100)
第二行，数字0、1组成的字符串；
输出：
第一行，数字m，表示分成m段。
接下来m行，每行包括一个切分出来的字符；（按照原字符串从左到右的顺序输出）
Examples
input
1
1
output
1
1
input
2
10
output
2
1 0
题目解析：
字符串组成只有0和1，最终的结果只有0的个数和1的个数相同，和不相同两种可能；
不相同，则直接满足题意；
相同的话，则切分出来第一个字符，剩下的字符串肯定0和1的数量不同。
int n;
char str[1111];
cin >> n;
cin >> str;
int x = 0, y = 0;
for (int i = 0; i < strlen(str); ++i) {
if (str[i] == '0') {
++x;
}
else {
++y;
}
}
if (x != y) {
cout << 1 << endl;
cout << str << endl;
}
else {
cout << 2 << endl;
cout << str[0] << " " << str + 1 << endl;
}
题目2
题目链接
题目大意：
给出n个数字，用n个数字拼成一个环，要求每个数字比相邻数字之和要小。
1,4,5,6,7,8这几个数字，左边是分配是合理的，右边的分配是不合理的
输入：
第一行，𝑛 (3≤𝑛≤10^5)
第二行，n个数字 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤10^9)
输出：
如果无解输出"NO"；
如果有解则输出"YES"，接下来一行输出n个数字，第1个和第n个认为是相连的。
Examples
input
3
2 4 3
output
YES
4 2 3
input
5
1 2 3 4 4
output
YES
4 4 2 1 3
input
3
13 8 5
output
NO
题目解析：
当某个数字很大的时候，比任意两个数字的和都大时，无解；
从题目的条件来看，数字越大则越难分配，数字越小则容易分配，数字最小的数肯定可以满足题目要求。
因为题目的数字是无序的，可以先对数字进行一个排序。（假如是从大到小）
我们先拿出一个最大的数字a[0]，将a[1]和a[2]分配到a[0]的两侧：
a[0]
/ \
a[1] a[2]
如果a[0]>=a[1]+a[2]，则无解。
因为a[1]<a[0]，所以a[1]肯定满足条件。
按照上面的思路，可以每次拿出两个数字，填充到两侧。
最后将两侧的数据串联起来，则形成一个环。
只要满足a[0]<a[1]+a[2]，则整个环都会满足题目的要求。
实现的过程，可以用deque（双端队列来模拟这个过程）
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
if (a[n - 1] >= a[n - 2] + a[n - 3]) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
bool isBack = 0;
for (int i = n - 1; i >= 0; --i) {
if (isBack) {
q.push_back(a[i]);
}
else {
q.push_front(a[i]);
}
isBack = !isBack;
}
for (int i = 0; i < n; ++i) {
cout << q.front() << " ";
q.pop_front();
}
cout << endl;
}
题目3
题目链接
题目大意：
有n个数字组成的数组𝑎1, 𝑎2, ..., 𝑎𝑛;
找到一个数字a[k]，k尽可能的小，并且满足：
1、a[k]比k往左边x个数字小；
2、a[k]比k往右边y个数字大；
输入：
第一行， 𝑛, 𝑥 and 𝑦 (1≤𝑛≤100000, 0≤𝑥,𝑦≤7)
第二行，n个数字，𝑎1, 𝑎2, ..., 𝑎𝑛 (1≤𝑎𝑖≤1e9),；
输出：
满足要求的，最小的索引k；（题目保证数据存在）
Examples
input
10 2 2
10 9 6 7 8 3 2 1 4 5
output
3
题目解析：
x/y数据范围较小，直接遍历判断，注意边界情况处理。
int n, x, y;
cin >> n >> x >> y;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
bool ok = 1;
for (int j = i + 1; j <= i + y && j < n; ++j) {
if (a[j] <= a[i]) {
ok = 0;
}
}
for (int j = i - 1; j >= i - x && j >= 0; --j) {
if (a[j] <= a[i]) {
ok = 0;
}
}
if (ok) {
cout << i + 1 << endl;
return 0;
}
}
题目4
题目链接
题目大意：
有一朵睡莲漂浮在水面上，睡莲超过水面距离为H；
随着河水的流动，睡莲刚好触碰水面，此时睡莲的移动距离为L；
已知睡莲的根部为A点。
问，水的深度是多少；
输入：
两个整数 𝐻 and 𝐿 (1≤𝐻<𝐿≤1e6)
输出：
水的深度，误差不超过10^-6。
Examples
input
1 2
output
1.5000000000000
题目解析：
设 x 为湖的深度。
(x + h)^2 = (x^2 + L^2)
x^2 + 2xh + h^2 = x^2 + L^2
2xh + h^2 = L^2
x = (L^2 - h^2) / 2h;
输出的参数可以为%.7f，保证误差不超过10^-6。
float h, l;
cin >> h >> l;
printf("%.7f", (l*l - h*h) / 2.0 / h);
题目5
题目链接
题目大意：
MP3文件是一个个整数组成，假设是n个非负整数；
数组中假如有K个不同的整数，那么每个数字需要𝑘=⌈log2𝐾⌉的bits来存储，那么整个文件需要的体积是n𝑘；
为了压缩MP3文件，我们可以选择两个数字l和r（l<r），然后对数组进行处理，如果数字在[l, r]中间则保持不变，小于l则变为l，大于r则变为r；
容易知道，改变的数字越多，MP3的音质则会越差。
现在已知硬盘上的空间有Ibytes（1byte=8bits），现在想知道最少改变多少个数字，可以使得该文件可以放置到硬盘；
输入：
第一行是两个整数 𝑛 and 𝐼 (1≤𝑛≤4⋅1e5, 1≤𝐼≤1e8)
第二行是n个整数 𝑎𝑖 (0≤𝑎𝑖≤1e9)
输出：
一个数字，表示最少的文字修改个数。
Examples
input
6 1
2 1 2 3 4 3
output
2
input
6 2
2 1 2 3 4 3
output
0
题目解析：
遍历一遍数组，我们可以知道K，然后计算得到k，最后计算体积nk；
如果体积不够，则我们需要改变数字；
按照题目的规则，我们改变的肯定是数组中最小或者最大的元素，数字的先后顺序没有意义，我们将数字进行一个排序；
由体积来反推，当我们知道Ibytes的总体积之后，我们可以估算出每个字的平均体积是(I*8/n)；
根据题意，我们知道数组中最多能有2^(I*8/n)个不同的数字，因为I比较大，这里为了避免超过int，我们可以认为最多有100w个不同的数字；
这样，当数组排好序之后，我们也知道数组中存在K个不同的数字，那么可以先预处理出每个数字的个数，然后枚举k个连续的不同数字的起始坐标x，在(x, x+K)之内的数字个数。
整体的时间复杂度是O(NlogN)，耗时主要是排序。
注意：
TLE 一次，用了cin；改为scanf可以避免；（因为数字都很大，用cin耗时比较长）
RE 一次，判断数组长度时候没有用vec.size，而是用了n；
int n, m;
cin >> n >> m;
int k = pow(2, min(20, m * 8 / n));
// k different numbers
for (int i = 0; i < n; ++i) {
int t;
scanf("%d", &t);
cnt[t]++;
if (cnt[t] == 1) {
vec.push_back(t);
}
}
sort(vec.begin(), vec.end());
int sum = 0, maxSum = 0;
for (int i = 0; i < vec.size() && i < k; ++i) {
sum += cnt[vec[i]];
}
maxSum = sum;
for (int i = k; i < vec.size(); ++i) {
sum += cnt[vec[i]] - cnt[vec[i - k]];
maxSum = max(maxSum, sum);
}
cout << n - maxSum << endl;
总结
这次思考题较多，还有很明显的数学题；
整体的代码量很少，非常适合动脑思考🤔。
网友评论