2 条题解
-
2
题意
给两个长度为n的数组
每次交换的位置之差不超过k
问最少换多少次使得s1,s2相同
贪心
我们发现每次交换的距离是一定的
所以我们要使得每次交换的额外消耗最小
所以我们每次要选%k最小的
code
#include <bits/stdc++.h> using namespace std; inline long long r(){ long long x = 0, f = 1; char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)){ x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } inline void w(long long x){ if(x < 0) { putchar('-'); x = -x; } if(x >= 10) w(x/10); putchar(x%10+'0'); } long long n, k; string a, b; void read(){ n = r(); k = r(); cin >> a >> b; a = " " + a; b = " " + b; return ; } multiset<pair<long long,long long> > s[2]; long long solve(long long x,long long i){ if(!s[x].size()){ s[x^1].insert({i%k,i}); return 0; } auto it = s[x].lower_bound({i%k,0}); if(it == s[x].end()) it = s[x].begin(); long long ans = (i - (it -> second) + k - 1) / k; s[x].erase(it); return ans; } void compute(){ long long ans = 0; for(long long i = 1;i <= n; i++){ if(a[i] != b[i]){ ans += solve((a[i]-'0')^1,i); } } cout << ans; } void init(){ } int main(){ read(); compute(); return 0; }-
Tim_justforsure
@ 2025-3-24 13:00:58
? 太详细了
-
Tim_justforsure
@ 2025-3-24 13:01:15
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @
-
- 1