程序员进阶之算法练习（五十八）
正文
题目1
题目链接
题目大意：
输入两个整数a和b，每次操作可以使得a=a+1；
问最少要几次操作，可以使得a可以整除b；
输入：
第一行整数t，表示样例个数； (1≤𝑡≤10000)
接下来t个样例，每个样例一行，有两个整数a、b；(1≤a，b≤10^9)
输出：
最少操作次数；
Examples
input
5
10 4
13 9
100 13
123 456
92 46
output
2
5
4
333
0
题目解析：
为了便于描述，下面用x和y来代替a和b；
如果x<=y，那么操作数就是y-x；
如果x>y，那么可以直接判断x%y==0，不满足则++x；
但是如果这样直接算，这个过程比较慢。在x%y!=0，不断x=x+1的时候，可以确定x/y的结果就是(x+y)/y取整；
那么最小操作次数就是(x + y) / y * y - x 。
int a[N];
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int x, y;
cin >> x >> y;
if (x <= y) {
cout << y - x << endl;
}
else {
if (x % y == 0) {
cout << 0 << endl;
}
else {
cout << (x + y) / y * y - x << endl;
}
}
}
return 0;
}
题目2
题目链接
题目大意：
有一个长度为n的字符串，有n-2个字符a，有2个字符b；
把这个字符串重新排列，可以若干个字符串，然后按字典序排列，比如说n=5的时候：
aaabb
aabab
aabba
abaab
ababa
abbaa
baaab
baaba
babaa
bbaaa
现在想知道长度为n的字符串重新排列后，第k个字符串是什么；
输入：
第一行整数t，表示样例个数； (1≤𝑡≤10000)
接下来t个样例，每个样例一行，有两个整数 𝑛 and 𝑘 (3≤𝑛≤105,1≤𝑘≤min(2⋅109, 𝑛⋅(𝑛−1)/2)
输出：
最少操作次数；
Examples
input
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100
output
aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa
题目解析：
从n=5样例，我们只看字符b，会从最后面开始，逐渐往前面排；
可以总结出规律，第1个b往前面挪动位置时，分别有：1、2、3、...、n-1种可能；
那么累计这个数字和sum，直到数字sum大于k，此时找到b的第1个位置；
接下来用sum和k的差值，就可以计算第2个b的位置，剩下的字符就全部是a了；
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 = 1; i <= n; ++i) {
if (k > i) {
k -= i;
}
else {
int x = n - i - 1, y = n - k;
for (int j = 0; j < n; ++j) {
if (j == x || j == y) {
putchar('b');
}
else {
putchar('a');
}
}
puts("");
break;
}
}
}
return 0;
}
题目3
题目链接
题目大意：
一个字符串，如果没有连续两个字符是相同的，则称为美丽的字符串；
给出一个字符串s，包括a/b/c/?，四种字符；
现在需要把每个?字符，分别填入a/b/c字符中的一个；
输入：
第一行 𝑡，表示样例数 (1≤𝑡≤1000)
每个样例一行，字符串𝑠 包括 'a', 'b', 'c' 和 '?'四种字符，字符串长度不超过10e5。
输出：
如果有解，则输出填充过后的字符串；
如果无解，则输出-1；
input
3
a???cb
a??bbc
a?b?c
output
ababcb
-1
acbac
题目解析：
首先是可以通过动态规划来解决，dp[i][j]=0/1表示第i个字符为a、b、c（j=0/1/2）是否有解；
当s[i]=='?'时，则可以生成d[i][0]、d[i][1]、d[i][2]三种状态，状态转移方程比较直接。
但是，题目还有另外一种解法：
对于字符串中的?字符，假如某个位置只有一个?连续，则只需考虑相邻的字符，填入一个不冲突的字符填入即可；
如果有多个?连续，因为连续?的相邻字符最多只有两种，但是?可以填入三种字符，则?必然可以填入一个字符，使得三个字符不连续相同；
那么，什么情况下会出现-1的情况？
幸好题目给出了样例：原来的字符就有相同字符的情况。
char a[N];
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
scanf("%s", a);
int n = (int)strlen(a);
for (int i = 0; i < n; ++i) {
if (a[i] == '?') {
bool vis[3] = {0};
if (i - 1 >= 0) {
vis[a[i-1] - 'a'] = 1;
}
if (i + 1 < n && a[i + 1] != '?') {
vis[a[i+1] - 'a'] = 1;
}
for (int j = 0; j < 3; ++j) {
if (!vis[j]) {
a[i] = 'a' + j;
}
}
}
}
bool ok = 1;
for (int i = 1; i < n; ++i) {
if (a[i] == a[i - 1]) {
ok = 0;
}
}
if (ok) {
printf("%s\n", a);
}
else {
puts("-1");
}
}
return 0;
}
题目4
题目链接
题目大意：
给出1~n的n个整数组成的数组，每个数字都只有一个；
我们把数字i称为beautiful，如果能够在数组中找到一段连续的数字，这个区间内的数字是1到i；
比如说对于数组[4,5,1,3,2,6]，我们能找到：
[1], [1,3,2], [4,5,1,3,2],[4,5,1,3,2,6] 这四个区间，所以数字1、3、5、6是beautiful，数字2、4不是beautiful；
现在给出一个1~n组成的数组，问数组中有哪些数字是beautiful；
输入：
第一行 𝑡 (1≤𝑡≤1000) 表示接下来有t个样例
每个样例的第一行是𝑛 (1≤𝑛≤2⋅10^5），表示数组的长度；
接下来一行是n个整数；
输出：
每一个样例输出一行长度为n的字符串，每个字符都是01组成，第i个字符为1表示第i个数字是beautiful；
input
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2
output
101011
11111
1001
题目解析：
看到题目的第一想法是从小到大排序，然后从1开始枚举数字；
对于某个数字x，如果左边数字比x小，则合并到集合x；
如果右边的数字比x小，则合并到集合x；
这样不断枚举，不断合并，通过集合的元素和x是否相同，就可以判断是否存在解。（对应下面解法A）
更优解：
对于数字k是否有解，其实是看[1, k]这个区间内，所有数字的左边界和右边界的距离，是否刚好等于数字k；
比如说k=3，[1,2,3]三个数字的左边界是3（对应1的位置），右边界是5（对应2的位置），距离是 (5-3+1)=3，所以k=3有解；
比如说k=4, [1,2,3,4]四个数字的左边界是1（对应4的位置），右边界是5（对应2的位置），距离是 (5-1+1)=5≠k，所以k=4无解。（对应下面解法B）
class SolutionA {
int a[N];
int fat[N];
int cnt[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int find(int x) {
if (fat[x] == x) {
return x;
}
int ret = find(fat[x]);
if (ret != fat[x]) {
fat[x] = ret;
cnt[ret] += cnt[x];
cnt[x] = 0;
}
return fat[x];
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx > fy) {
fat[fx] = fy;
cnt[fy] += cnt[fx];
cnt[fx] = 0;
}
else {
fat[fy] = fx;
cnt[fx] += cnt[fy];
cnt[fy] = 0;
}
find(x);
find(y);
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
while (!q.empty()) {
q.pop();
}
memset(fat, 0, sizeof(fat));
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i) {
q.push(make_pair(a[i], i));
}
while (!q.empty()) {
pair<int, int> tmp = q.top();
tmp = q.top();
q.pop();
fat[tmp.first] = tmp.first;
cnt[tmp.first] = 1;
int l = tmp.second - 1;
if (l >= 0 && a[l] < tmp.first) {
merge(a[l], tmp.first);
}
int r = tmp.second + 1;
if (r < n && a[r] < tmp.first) {
merge(a[r], tmp.first);
}
if (cnt[find(tmp.first)] == tmp.first) {
putchar('1');
}
else {
putchar('0');
}
}
puts("");
}
}
}ac;
class SolutionB {
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int x;
scanf("%d", &x);
a[x-1] = i;
}
int left = n, right = 0;
for (int i = 0; i < n; ++i) {
left = min(left, a[i]);
right = max(right, a[i]);
if (right - left == i) {
cout << "1";
}
else {
cout << "0";
}
}
cout << endl;
}
}
}ac_fast;
题目5
题目链接
题目大意：
举办一场比赛，有n个人参加比赛，并得到了n个分数p[i]；
现在需要分配金银铜牌的数量分别为g、s、b个，有以下要求：
金银铜的数量必须有一个；（𝑔>0 , 𝑠>0 and 𝑏>0)）
金牌人数要少于银牌和铜牌；（𝑔<𝑠 and 𝑔<𝑏）
金银铜的分数，必须严格减少，金牌分数>银牌分数>铜牌分数>没得奖的分数；
获奖人数不超过总人数的一半；( 𝑔+𝑠+𝑏≤n/2）
输入：
第一行𝑡，表示有t个样例 (1≤𝑡≤10000)
每个样例有两行
第一行 𝑛 (1≤𝑛≤4⋅1e5)
第二行 𝑝1,𝑝2,…,𝑝𝑛 (0≤𝑝𝑖≤1e6， 𝑝1≥𝑝2≥⋯≥𝑝𝑛 )
输出：
每个样例输出一行，三个整数𝑔,𝑠,𝑏；
g=s=b=0表示无法分配；
否则输出g、s、b分别表示金银铜牌的数量。
input
5
12
5 4 4 3 2 2 1 1 1 1 1 1
4
4 3 2 1
1
1000000
20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
32
64 64 63 58 58 58 58 58 37 37 37 37 34 34 28 28 28 28 28 28 24 24 19 17 17 17 17 16 16 16 16 11
output
1 2 3
0 0 0
0 0 0
2 5 3
2 6 6
题目解析：
总结一下题目的意思：
金银铜铁，共需要4个分数（铁牌表示无得奖）；
金牌人数要少于银牌和铜牌；
金银铜加起来不超过一半；
希望获奖的人尽可能多；
将数字去重，按照数字大小排序，每个数字有一个权值，权值就是人数；
相当于把数组切分成a、b、c、d共4段，要求sum(a)<sum(b) & sum(a)<sum(b)，并且sum(a+b+c)尽可能的大，又不超过权值总和的1/2；
假设新的数组排序之后是s[1~m]，金牌只需要有最少的人数，那么就是s[1]；
从题目的要求来分析，s[1]是分给金牌，s[2~x]分给银牌，x的求法就是直接遍历，累计银牌人数大于金牌；
同理，铜牌的人数也要大于金牌，然后就可以不断遍历，只要满足s[1], s[2], s[3] 之和小于n/2；
剩下所有人分给铁牌。
map<int, int> h;
vector<int> s;
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
h.clear();
while (!s.empty()) {
s.pop_back();
}
for (int i = 0; i < n; ++i) {
int k;
scanf("%d", &k);
++h[k];
}
for (map<int, int>::iterator iter = h.begin(); iter != h.end(); ++iter) {
// cout << iter->first << " " << iter->second << endl;
s.push_back(iter->second);
}
int ans[3] = {0};
if (s.size() >= 4) {
int x = s.back();
s.pop_back();
int y = 0;
while (x >= y && !s.empty()) {
y += s.back();
s.pop_back();
}
int z = 0;
while (x >= z && !s.empty()) {
z += s.back();
s.pop_back();
}
while (x + y + z <= n / 2) {
ans[0] = x;
ans[1] = y;
ans[2] = z;
if(s.empty()) {
break;
}
z += s.back();
s.pop_back();
}
}
cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
}
return 0;
}
