【牛客周賽 Round 9】C D
https://ac.nowcoder.com/acm/contest/63869#question
C
https://ac.nowcoder.com/acm/contest/63869/C
題意
小美定義一個 01 串的權值為：每次操作選擇一位取反，使得相鄰字符都不相等的最小操作次數。
例如，"10001"的權值是 1，因為只需要修改一次：對第三個字符取反即可。
現在小美拿到了一個 01 串，她希望你求出所有非空連續子串的權值之和，你能幫幫她嗎？
題解
1.暴力求 O(n^3) TLE
2.預處理 O(n^2) 僅枚舉區間
code
點擊查看代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
// const int N = 1e5 + 10;
int n;
char s[2005];
int a[2005], b[2005];
int fa[2005], fb[2005];
int main(){
scanf("%s", s + 1); n = strlen(s + 1);
a[0] = 0; b[0] = 1;
for(int i = 1; i <= n; i++) {
a[i] = (a[i - 1] ^ 1);
b[i] = (b[i - 1] ^ 1);
fa[i] = fa[i - 1] + (s[i] - '0' != a[i]);
fb[i] = fb[i - 1] + (s[i] - '0' != b[i]);
}
ll ans = 0;
for(int L = 1; L <= n; L++) {
for(int R = L; R <= n; R++) {
ans += min(fa[R] - fa[L - 1], fb[R] - fb[L - 1]);
}
}
printf("%lld\n", ans);
return 0;
}
D
https://ac.nowcoder.com/acm/contest/63869/D
題意
小美拿到了一個數組，她每次可以進行如下操作：
選擇兩個元素，一個加 1，另一個減 1。
小美希望若干次操作后，眾數的出現次數盡可能多。你能幫她求出最小的操作次數嗎？
題解
眾數出現的次數，要么是 n，要么是 n-1.
是n的情況：平均數是整數，那么把所有數都變成平均數
是n-1的情況：先把數組排序，要么是前n-1個數的平均數，要么是后n-1個數
code
點擊查看代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
ll ans = 0;
int main(){
ios::sync_with_stdio(false);
cin >> n;
ll s = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i]; s += a[i];
}
sort(a + 1, a + n + 1);
ll ave = s / n;
int more = s - 1ll * ave * n; // ave n-more ave+1 more
if(more == 0) {
for(int i = 1; i <= n; i++) {
if(a[i] < ave) ans += ave - a[i];
else break;
}
cout << ans << endl;
return 0;
}
ans = 1e18;
// 前n-1
ll tem = s - a[n]; tem /= (n - 1);
for(ll i = tem - 1; i <= tem + 1; i++) {
ll mn = 0, mx = 0;
for(int j = 1; j <= n - 1; j++) {
if(a[j] < i) mn += i - a[j];
else mx += a[j] - i;
}
ans = min(ans, max(mn, mx));
// cout << mn << ' ' << mx << ' ' << ans << endl; ///
}
// 后n-1
tem = s - a[1]; tem /= (n - 1);
for(ll i = tem - 1; i <= tem + 1; i++) {
ll mn = 0, mx = 0;
for(int j = 2; j <= n; j++) {
if(a[j] < i) mn += i - a[j];
else mx += a[j] - i;
}
ans = min(ans, max(mn, mx));
}
cout << ans << endl;
return 0;
}
浙公網安備 33010602011771號