题目1
题目链接
题目大意：
有这样的一个字符串，如图：
现在光标停留在最左边的数字1处，我们可以进行以下的操作：
1、将当前光标所在位置的数字输出；
2、移动光标到相邻的数字，比如说从1移动到2，从2移动到3；（1的左边不能移动，0的右边不能移动）
现在想知道，输出特定的4个字符，最少需要几次操作。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例一行，4个整数；
输出：
每个样例一行，输出最少的操作次数。
Examples
input
10
1111
1236
1010
1920
9273
0000
7492
8543
0294
8361
output
4
9
31
27
28
13
25
16
33
24
题目解析：
输出数字的最小操作方法:
1、将光标移到指定位置；
2、展示当前数字；
题目的意思非常简单，但是如果直接通过if去实现，在计算0的位置时，会比较繁琐；（因为数字0在最右边，破坏了字符和数字的对应关系）
这里有个实现的小技巧，我们将数字0看成10，那么整个数字序列就是从小到大。
这样在计算操作1的时候，就能通过数字相减直接得到结果。
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
char s[10];
cin >> s;
int cur = 1, ans = 4;
for (int i = 0; i < 4; ++i) {
int idx = s[i] - '0';
if (idx == 0) idx += 10;
ans += abs(cur - idx);
cur = idx;
}
cout << ans << endl;
}
}
}
ac;
题目2
题目链接
题目大意：
给出一个长度为n的字符串s，现在需要移除字符串中的k个字符，剩下的字符可以随意排列；
问，剩下的字符能否组成一个回文串？
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行，𝑛 and 𝑘 (0≤𝑘<𝑛≤1e5)
第二行，字符串s；（小写字母组成）
输出：
每个样例一行，如果有解则输出YES；如果无解则输出NO；
Examples
input
14
1 0
a
2 0
ab
2 1
ba
3 1
abb
3 2
abc
6 2
bacacd
6 2
fagbza
6 2
zwaafa
7 2
taagaak
14 3
ttrraakkttoorr
5 3
debdb
5 4
ecadc
5 3
debca
5 3
abaac
output
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES
题目解析：
最终的字符串可以任意调整顺序，那么重点在于每个字符的数量；
题目是要求构造回文串，如果某个字符数量是偶数，那么可以组成回文串；如果某个字符数量是奇数，那可能会导致无法构成回文串。
假设统计所有字符的数量，有x个偶数字符，有y个奇数字符；那么能构成回文串的条件就是y<=1；（如果只有1个奇数，可以把多出来这个字符放在回文串中间）
由于题目增加了一个限制，要去除k个字符，那么奇数字符就可以有更多（因为移除时优先移除奇数字符），所以最终条件是y<=1+k；
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
string s;
cin >> n >> k;
cin >> s;
vector<int> cnt(26);
for (int i = 0; i < n; ++i) cnt[s[i] - 'a']++;
int y = 0;
for (int i = 0; i < 26; ++i) y += (cnt[i] % 2);
if (y <= 1 + k) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
}
ac;
题目3
题目链接
题目大意：
有n个整数的数组a，再给出整数k；
现在可以进行任意次以下操作：
选择某个数组元素，将该元素+1；
现在要求数组最终的乘积，能够整除数字k，问最少需要操作多少次；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行，𝑛 and 𝑘 (2≤𝑛≤1e5 , 2≤𝑘≤5 )
第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤10).
输出：
每个样例一行，输出最小的操作次数。
Examples
input
15
2 5
7 3
3 3
7 4 1
5 2
9 7 7 3 9
5 5
5 4 1 2 3
7 4
9 5 1 5 9 5 1
3 4
6 3 6
3 4
6 1 5
3 4
1 5 9
4 4
1 4 1 1
3 4
3 5 3
4 5
8 9 9 3
2 5
1 6
2 5
10 10
4 5
1 6 1 1
2 5
7 7
output
2
2
1
0
2
0
1
2
0
1
1
4
0
4
3
题目解析：
第一反应，是将k进行因数分解，然后将数字分配到对应因数，还要考虑一个数字对应多个因数的情况（比如说a1=25，可以对应到两个因数5）；
这样题目整体处理会比较麻烦。
考虑到k的数据范围很小，因数情况也只有4=2x2的可能，可以不使用这种方法来处理。
假如k=2时，如果数组a存在偶数，则ans=0，否则ans=1；
假如k=3时，判断每个数组元素与3的余数即可，如果有能整除，则ans=0，否则为ans=3-最大余数；
假如k=4时，按照2的因数来算，比如说4就算2个，如果数组中存在2个，那么ans=0；如果数组中存在1个，那么ans=1（因为必然还有一个奇数，这个奇数可以+1得到偶数）；如果数组中存在0个，那么ans=2（因为有两个数字，必定是2个奇数）；（同时也可以按照k=3的做法，计算下如果累加每个数字的情况，取较小者）
假如k=5时，可以按照k=3的做法来；
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int ans = 0, cnt = 0;
while (n--) {
int tmp;
cin >> tmp;
if (tmp % k) ans = max(ans, tmp % k);
else ans = k;
while (tmp % 2 == 0) {
++cnt;
tmp /= 2;
}
}
if (k == 4) {
if (cnt >= 2) cout << 0 << endl;
else cout << min(k - ans, 2 - cnt) << endl;
}
else {
cout << (k - ans) << endl;
}
}
}
}
ac;
题目4
题目链接
题目大意：
有n个整数的数组𝑎1,𝑎2,…,𝑎𝑛
现在可以对数组进行多次下述操作：
选择数组中的某个整数𝑎𝑖，如果𝑎𝑖<0 则可以把𝑎𝑖替换为[𝑎𝑖,0]区间中的整数；如果𝑎𝑖>0，则可以把𝑎𝑖替换为 [0,𝑎𝑖] 区间中的整数.
现在想知道最少需要多少次操作，才能使得最终数组所有数字的乘积尽可能的小；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤500)
每个样例2行
第一行，整数𝑛(1≤𝑛≤100)
第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛(−1e9≤𝑎𝑖≤1e9).
输出：
每个样例第一行，输出需要的操作次数x；
接下来每个操作一行，输出参数i和x，表示将a[i]设置为x；
Examples
input
4
1
155
4
2 8 -1 3
4
-1 0 -2 -5
4
-15 -75 -25 -30
output
1
1 0
0
0
1
3 0
题目解析：
题目的要求的是乘积尽可能小，如果数组当前乘积结果是正数，那么将任意一个数字变为0，结果就是最小值0；
如果当前乘积是数字0，那么不管如何修改，最终结果都是0；
如果当前乘积是数字负数，那么修改任何数字，都可能会让结果更大，而不是更小。
思路想清楚，代码就很简单了。
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int zero = 0, cnt = 0;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) {
if (a[i] == 0) ++zero;
else if (a[i] < 0) ++cnt;
}
if (cnt % 2 || zero) cout << 0 << endl;
else cout << "1\n 1 0" << endl;
}
}
}
ac;
题目5
题目链接
题目大意：
有n个整数区间[𝑙1,𝑟1],[𝑙2,𝑟2],…,[𝑙𝑛,𝑟𝑛]，每个区间有一个系数 𝑐𝑖，每个区间的重量为𝑐𝑖⋅(𝑟𝑖−𝑙𝑖).
现在可以进行下列操作：
1、任意调换n个整数区间，左区间l的数字；
2、任意调换n个整数区间，右区间r的数字；
3、任意调换n个整数区间，系数c的数字；
要求调换完，每个区间 [𝑙𝑖, 𝑟𝑖] 都满足 𝑙𝑖 < 𝑟𝑖;
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例有4行
第一行，整数 𝑛 (1≤𝑛≤2e5)
第二行，整数 𝑙1,𝑙2,…,𝑙𝑛(1≤𝑙𝑖≤2⋅1e5)
第三行，整数 𝑟1,𝑟2,…,𝑟𝑛 (𝑙𝑖<𝑟𝑖≤2⋅1e5)
第四行，整数𝑐1,𝑐2,…,𝑐𝑛 (1≤𝑐𝑖≤1e7 )
题目保证，{𝑙1,𝑙2,…,𝑙𝑛,𝑟1,𝑟2,…,𝑟𝑛}数字各不相同。
输出：
每个样例一行，输出调整后，所有区间的最小重量和。
Examples
input
2
2
8 3
12 23
100 100
4
20 1 2 5
30 4 3 10
2 3 2 3
output
2400
42
题目解析：
题目允许对l、r、c进行任意调换，那么可以先对l、r、c进行从小到大排序，便于分析问题。
接下来做数据分析，先考虑n=2的情况
a1 a2
b1 b2
c1 c2
正常情况下 (b1-a1)c1 + (b2 - a2)c2
先考虑c1和c2的情况，假设b1-a1和b2-a2相等，那么调换c1和c2对于结果没有影响。
假设b1-a1<b2-a2呢？ 这次c1<c2就会导致更小的结果，应该把更大的数字放在前面。
延伸分析，假设有若干个区间长度，那么可以将区间长度从小到大排序，接着把c越大的匹配到越前面的结果。
接下来，就是怎么匹配出来若干个区间长度，并且保证结果符合要求。
首先还是从2个区间开始分析
a1 a2
b1 b2
我们知道最终两个区间的和，不管如何交换，必然是 (b1 - a1) + (b2 - a2)。
那在这种情况下，我们让其中一个区间尽可能小，另外一个区间必然会增大。
沿着这个贪心思路，我们只需要每次让右区间，去匹配到尽可能接近的左区间。
有一个简单实现方案，对于每一个左区间（从大到小开始），我们从大到小去遍历右区间，找出来一个最近的节点。
但是这样的复杂度是O(N x N)；
我们可以引入优先队列来简化操作，在选择右区间的时候，big队列表示前面选择过的节点队列，从大到小排列，这样就可以直接从big队列中找到之前遍历过的最大值；
backup表示还没有被选择过的节点，从小到大排列，这样当big队列最大值都无法满足要求，就需要从backup中取数字。
这样整体的复杂度就可以降低到NlogN的级别。
class Solution {
static const int N = 201010;
priority_queue<int> big;
priority_queue<int, vector<int>, greater<int> > backup;
int a[N], b[N], c[N], diff[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
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 < n; ++i) cin >> c[i];
sort(a, a + n);
sort(c, c + n);
for (int i = 0; i < n; ++i) backup.push(b[i]);
for (int i = n - 1; i >= 0; --i) {
int cur = 0;
if (!big.empty()) {
cur = big.top();
}
if (cur < a[i]) { // 当前big堆里不满足
while (cur < a[i]) {
cur = backup.top();
big.push(cur);
backup.pop();
}
big.pop();
}
else {
big.pop();
while (big.size() && big.top() > a[i]) {
backup.push(cur);
cur = big.top();
big.pop();
}
}
diff[i] = cur - a[i];
}
sort(diff, diff + n);
lld ans = 0;
for (int i = 0; i < n; ++i) ans += diff[i] * 1LL * c[n - 1 - i];
cout << ans << endl;
}
}
}
ac;
