程序员进阶之算法练习（五十七）
正文
题目1
题目链接 题目大意： 有1xn的棋盘（n为偶数），棋盘上的格子颜色为黑白交替；（BWBWBW..BW这样分布，B表示黑，W表示白) 现在已经有n/2个棋子放置在棋盘上，每个格子只能放置1个棋子； 每一步可以移动一个棋子向左或者向右，但是不能移到已经被棋子占有的格子； 现在需要把棋子移动到同一个颜色的格子上面，问最少需要多少步。
输入数据： 第一行 n (2 ≤ n ≤ 100, n是偶数) 第二行 n/2个数字p[i]，表示已经放置棋子的格子 (1 ≤ p[i] ≤ n)
Examples input 6 1 2 6 output 2
题目解析： 只有两种可能，全部移到黑色or全部移到白色的代价； 因为数量较小，直接算出来两种可能的最小步数。
怎么计算移到黑色的最小步数？ 因为只有n/2个黑色格子，最终的布局必然是1、3、5、7这样的格局； 那么可以采用这样的策略： 先把第一个移到1、第二个移到3...
思考🤔： trick: 给出的位置p[i]是无序的。
int main(int argc, const char * argv[]) {
// insert code here...
int n;
cin >> n;
for (int i = 1; i <= n/2; ++i) {
cin >> a[i];
}
sort(a + 1, a + 1 + n / 2);
int costB = 0, costW = 0;
for (int i = 1; i <= n; ++i) {
if (i % 2) {
costB += abs(i - a[(i+1)/2]);
}
else {
costW += abs(i - a[(i+1)/2]);
}
}
cout << min(costB, costW) << endl;
return 0;
}题目2
题目链接 题目大意： 有n个开关，m个灯； 开始时，m个灯是处于关闭状态； 一个开关可以对应多个灯，我们用二维数组a[i][j]来表示第i个开关按下之后第j个灯的状态，1表示打开，0表示无反应； 如果按下按钮可能会有多个灯被打开，灯就会一直处于打开的状态，即使其他控制这个灯的开关被按下； 问，是否存在无用开关（即使不用这个开关也能打开m个灯）？ 如果有，输出YES；否则输出NO。
输入数据： 第一行 n and m (1 ≤ n, m ≤ 2000) 接下来是n*m的矩阵，表示a[i][j]；
Examples input 4 5 10101 01000 00111 10000 output YES
题目解析： 枚举每个开关不打开，其他开关全部按下的情况，看是否灯全亮。 但是这样的复杂度是O(N ^ 3) = 2000 ^ 3 = 8 * 10 ^ 9，这个数量级已经超过时间限制。 留意到，这个复杂度里面有很多是重复计算，比如说我们在枚举开关2、3不打开的时候，会计算俩遍第1个开关对应的灯； 那么这个算法存在O(N)的优化空间。 从这里去思考，可以得到优化方案： 先把每个灯能控制的开关数加起来，用ans[i]表示控制灯i亮的开关数量； 当枚举某个开关不打开的时候，只要看看他控制的灯是不是ans[i]>1即可。
int main(int argc, const char * argv[]) {
// insert code here...
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> (a[i] + 1);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
ans[j] += (a[i][j] == '1');
}
}
for (int i = 1; i <= n; ++i) {
int ok = 1;
for (int j = 1; j <= m; ++j) {
if (a[i][j] == '1' && ans[j] <= 1) {
ok = 0;
break;
}
}
if (ok) {
cout << "YES" << endl;
return 0;
}
}
cout << "NO" << endl;
return 0;
}题目3
题目链接 题目大意： 有m个木板，每个木板有一个长度a[i]； k个木板可以组成一个木桶，根据木桶原理知道，最短的木板决定容量，我们用最短木板的长度来表示容量； 现在需要用m个木板来组成n个木桶，已知m=n*k； 现在要求任意桶之间的容量差不能超过l，问组成的n个桶的最大容量和是多少？
输入数据： 第一行 n, k and l (1 ≤ n, k ≤ 1e5, 1 ≤ n·k ≤ 1e5, 0 ≤ l ≤ 1e9). 第二行 m个数字（m=n*k）a[i]，表示第i个木板的长度；
输出： 如果满足要求，n个桶的最大容量和； 如果不满足要求，则输出0.
Examples input 4 2 1 2 2 1 2 3 2 2 3 output 7
题目解析： 如果没有要求，任意组成n个木桶，怎样才能使得容量和最大？ 思路：因为所有木板都要参与组成木桶，那么最短的那块木板所在的木桶必然受到这个影响； 所以，我们可以把木板排序，然后从小到大的选择木板组成木桶，即可得到最大容量和。
再考虑题目要求，容量差不能超过l； 先对数组a[i]排序，从小到大； 第一个桶容量只能是a[1]，剩下的桶必须选一块木板长度在(a[1], a[1]+l)之间； 根据上面贪心的经验，我们可以在(a[1], a[1]+l)区间内中选择最大的一块木板，然后在区间外选择任意木板组成木桶； 接着重复在(a[1], a[1]+l)区间内中选择最大的一块木板，接着在区间外选择任意木板组成木桶，如果区间外的木桶不够，则使用区间内的木桶，同样是大者优先； 这样可以得到满足要求的n个木桶的最大容量和。
对上面的思路进行整理： 排序后的a[i]，如果(a[1], a[1]+l)存在n个木板，那么必然存在解； 对于第i个木桶，假设其最短的木板是a[x]，优先考虑(a[x], a[1]+l)选择木板，但是要保证区间剩余木板数量>=(n-i)个木板。
int main(int argc, const char * argv[]) {
// insert code here...
lld n, k, l;
cin >> n >> k >> l;
lld m = 1LL * n * k;
for (lld i = 1; i <= m; ++i) {
cin >> a[i];
}
sort(a + 1, a + 1 + m);
lld sum = 0;
for (lld i = 1; i <= m; ++i) {
if (a[i] <= a[1] + l) {
++sum;
}
else {
break;
}
}
if (sum >= n) {
lld curIndex = 0, curCount = 0;
lld ans = 0;
while (curCount < n) {
++curIndex;
++curCount;
--sum; // curIndex对应的木板已经使用
ans = ans + a[curIndex];
if (sum > (n - curCount)) { // 剩余木板足够
lld s = sum - (n - curCount);
curIndex += min(s, k - 1);
sum -= min(s, k - 1);
}
}
cout << ans << endl;
}
else {
cout << 0 << endl;
}
return 0;
}题目4
题目链接 题目大意： 给出n个数字表示n个山峰的高度，这n个山峰排成一行； 每次从最左边放上一个石头，如果这个山峰的高度比右边的小，则这个山峰（乐高积木）加一； 如果这个山峰的高度 大于等于 右边的山峰，则石头会滚向右边的山峰； 下个山峰再重复这个过程，直到最右边的山峰；如果石头到达最右边一个山峰，则会继续滚下去，最右边的山峰高度不变。
输入： 第一行整数𝑡，表示t个样例 (1≤𝑡≤100) 每个样例有两行： 第一行 𝑛 and 𝑘 (1≤𝑛≤100; 1≤𝑘≤1e9) 第二行 ℎ1,ℎ2,…,ℎ𝑛 (1≤ℎ𝑖≤100)
输出： 每个样例输出一行，如果落出山峰则输出-1；否则输出具体的停留位置。
Examples input 4 4 3 4 1 2 3 2 7 1 8 4 5 4 1 2 3 3 1 5 3 1 output 2 1 -1 -1
题目解析： 题目的数据范围很小，可以直接模拟，枚举从第1个石头到第k个石头的位置。 但如果数据范围比较大呢？由于模拟的解法比较简单，这里分享一种数据量较大的情况的处理方法，具体可以见下面：
typedef long long lld;
const int N = 1000, M = 3010100, inf = 0x7fffffff;
const lld llinf = 0x7fffffff7fffffffll;
int a[N];
int b[N];
lld calcMaxCount(int left, int right) {
b[right] = 0;
lld sum = 0;
for (int i = right - 1; i >= 0; --i) {
b[i] = max(a[i], b[i + 1]);
sum += b[i] - a[i];
}
return sum;
}
// N * N的复杂度
int look(int left, int right, int k) {
if (left == right) {
return left;
}
int maxHeight = a[left];
for (int i = left + 1; i < right; ++i) {
maxHeight = max(maxHeight, a[i]);
}
lld sum = 0;
for (int i = left; i < right; ++i) {
sum += maxHeight - a[i];
}
if (k > sum) {
// 开始累积木
int pos = ((k - sum) % (right - left)); // maxHeight持平之后，必然第一个落在right-1，第二个是right-2
return pos == 0 ? left : (right - pos);
}
else {
// 不能全部达到maxHeight高度并且有剩余，那么根据maxHeight看看是落在左边，还是右边
lld leftSum = 0;
int maxPos = left + 1;
for (int i = left; a[i] != maxHeight; ++i) {
leftSum += maxHeight - a[i];
maxPos = i + 1;
}
if (leftSum >= k) {
int ret = look(left, maxPos, k);
return ret;
}
else {
int ret = look(maxPos, right, k - (int)leftSum);
return ret;
}
}
}
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];
}
lld sum = calcMaxCount(0, n);
// cout << sum << endl;
if (k > sum) {
cout << -1 << endl;
}
else {
cout << look(0, n, k) + 1 << endl;
}
}
return 0;
}题目5
题目链接 题目大意： 给出n个栅栏，每个栅栏有一个初始颜色a[i]，现在想把n个栅栏的颜色染成b[i]； 已知会有m个工人携带燃料c[j]先后过来，每个工人都必须对一个栅栏进行染色，并且工人染色的顺序会按照到达顺序（无法修改先后）；
如果最终n个栅栏都可以染成目标颜色，则输出YES，然后输出m个数字，分别表示m个工人先后对m个栅栏进行的染色； 如果最终无法都染成目标颜色，则输出NO；
输入： 第一行整数𝑡，表示有t个样例 (1≤𝑡≤1e4) 每个样例有四行 第一行 𝑛 and 𝑚 (1≤𝑛,𝑚≤1e5) 第二行𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛) 第三行 𝑏1,𝑏2,…,𝑏𝑛 (1≤𝑏𝑖≤𝑛) 第四行 𝑐1,𝑐2,…,𝑐𝑚 (1≤𝑐𝑗≤𝑛)
输出： 每个样例，如果无解则输出NO； 如果有解，则输出YES，然后第二行输出𝑚个整数𝑥1,𝑥2,…,𝑥𝑚，表示每个工人染色的位置。
Examples input 6 1 1 1 1 1 5 2 1 2 2 1 1 1 2 2 1 1 1 2 3 3 2 2 2 2 2 2 2 3 2 10 5 7 3 2 1 7 9 4 2 7 9 9 9 2 1 4 9 4 2 3 9 9 9 7 4 3 5 2 1 2 2 1 1 1 2 2 1 1 3 3 6 4 3 4 2 4 1 2 2 3 1 3 1 1 2 2 3 4
output YES 1 YES 2 2 YES 1 1 1 YES 2 1 9 5 9 NO NO
题目解析： 先找出数组a和数组b的差别，首先这些差别的颜色必须是数组c的子集，这样才有足够的颜色。 但是他们还有一个要求是工人的达到顺序，所以如果存在最后某些颜色无法使用，则仍然会导致最终颜色一致。
那么可以采用这样一种策略：如果最后一个工人的颜色是在数组b的第y个位置出现，那么前面所有不需要的颜色，都可以先放在位置y，等到最后一个工人把颜色刷成正确颜色； 如果最后一个工人的颜色和数组b没有相似的，那么这个工人必然会导致最终的颜色不一致，此时无解。
这里有一个小trick，在确定最后一个工人对应的位置y时，要优先选择a[y]!=b[y]的位置，避免浪费。
class Solution {
static const int N = 100010;
public:
int n, m;
int a[N], b[N], c[N], ans[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n >> m;
map<int, vector<int>> cnt;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
for (int i = 0; i < m; ++i) {
cin >> c[i];
ans[i] = -1;
cnt[c[i]].push_back(i);
}
int y = -1;
for (int i = 0; i < n; ++i) {
if (b[i] == c[m - 1] && b[i] != a[i]) { // no waste
y = i;
break;
}
}
for (int i = 0; i < n && y == -1; ++i) {
if (b[i] == c[m - 1]) { // useless color
y = i;
break;
}
}
bool ok = 1;
if (y == -1) {
ok = 0;
}
else {
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) { // search color
if (cnt[b[i]].size() > 0) {
ans[cnt[b[i]].back()] = i;
cnt[b[i]].pop_back();
}
else {
ok = 0;
break;
}
}
}
}
if (ok) {
for (int i = 0; i < m; ++i) {
if (ans[i] < 0) {
ans[i] = y;
}
}
cout << "YES" << endl;
for (int i = 0; i < m; ++i) {
cout << ans[i] + 1 << " ";
}
cout << endl;
}
else {
cout << "NO" << endl;
}
}
}
}
ac;