正文

题目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;