程序员进阶之算法练习（四十一）
正文
题目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;总结
这次思考题较多，还有很明显的数学题； 整体的代码量很少，非常适合动脑思考?。