<!–
.mycontent {
border-left-style: solid;
border-left-width: 10px;
border-left-color: rgb(70, 131, 255);
padding-left: 10px;
}
h3.subtitle {
padding-top: 3px;
padding-bottom: 3px;
background-color: rgba(70, 131, 255, 0.5);
}
.warning {
padding-left: 30px;
padding-top: 3px;
padding-bottom: 3px;
background-color: rgba(255, 255, 83, 0.5);
}
.theory {
padding-left: 30px;
padding-top: 3px;
padding-bottom: 3px;
background-color: rgba(0, 255, 64, 0.5);
}
.methon {
padding-left: 30px;
padding-top: 3px;
padding-bottom: 3px;
background-color: rgba(135, 206, 235, 0.5);
}
–>
题目传送门
题目大意
给定一个数组$a$和数组$b$,每次操作可以选择$a$的一个子区间将其中的数在模4意义下加1,问把$a$变成$b$的最少操作次数。
首先求$b – a$,再差分,令这个数组为$c$。
那么操作的次数是这个数组$c$中正数的和。
现在可以做的是选择一个地方+4,它后面的某个地方-4。
考虑什么时候可以使得当前的答案减少。
- 在$-3$处$+4$,在$3$处$-4$,答案减少2
- 在$-3$处$+4$,在$2$处$-4$,答案减少1
- 在$-2$处$+4$,在$3$处$-4$,答案减少1
首先我们将尽量靠后的$-3$和$3$匹配,然后将对它操作。
这个用一个栈就能做。
剩下就贪心一下就好了。注意当$-3$和$2$操作时会多出$-2$。
Code
/**
* bzoj
* Problem#3704
* Accepted
* Time: 1400ms
* Memory: 128316k
*/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
typedef bool boolean; typedef class Input {
protected:
const static int limit = ;
FILE* file; int ss, st;
char buf[limit];
public: Input():file(NULL) { };
Input(FILE* file):file(file) { } void open(FILE *file) {
this->file = file;
} void open(const char* filename) {
file = fopen(filename, "r");
} char pick() {
if (ss == st)
st = fread(buf, , limit, file), ss = ;//, cerr << "str: " << buf << "ed " << st << endl;
return buf[ss++];
}
}Input; #define digit(_x) ((_x) >= '0' && (_x) <= '9') Input& operator >> (Input& in, unsigned& u) {
char x;
while (~(x = in.pick()) && !digit(x));
for (u = x - ''; ~(x = in.pick()) && digit(x); u = u * + x - '');
return in;
} Input& operator >> (Input& in, unsigned long long& u) {
char x;
while (~(x = in.pick()) && !digit(x));
for (u = x - ''; ~(x = in.pick()) && digit(x); u = u * + x - '');
return in;
} Input& operator >> (Input& in, int& u) {
char x;
while (~(x = in.pick()) && !digit(x) && x != '-');
int aflag = ((x == '-') ? (x = in.pick(), -) : ());
for (u = x - ''; ~(x = in.pick()) && digit(x); u = u * + x - '');
u *= aflag;
return in;
} Input& operator >> (Input& in, long long& u) {
char x;
while (~(x = in.pick()) && !digit(x) && x != '-');
int aflag = ((x == '-') ? (x = in.pick(), -) : ());
for (u = x - ''; ~(x = in.pick()) && digit(x); u = u * + x - '');
u *= aflag;
return in;
} Input& operator >> (Input& in, char* str) {
for (char x; ~(x = in.pick()) && x != '\n' && x != ' '; *(str++) = x);
return in;
} Input in (stdin); template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} int n;
int *a, *b, *c;
boolean *used; inline void init() {
in >> n;
a = new int[(n + )];
b = new int[(n + )];
c = new int[(n + )];
for (int i = ; i <= n; i++) {
in >> a[i];
}
for (int i = ; i <= n; i++) {
in >> b[i];
c[i] = (b[i] - a[i] + ) % ;
}
} stack<int> sta;
inline void solve() {
int ans = ;
for (int i = n; i > ; i--)
c[i] = c[i] - c[i - ];
used = new boolean[(n + )];
pfill(used, used + n + , false);
for (int i = ; i <= n; i++)
if (c[i] > )
ans += c[i];
for (int i = , y; i <= n; i++)
if (c[i] == -)
sta.push(i);
else if (c[i] == && !sta.empty()) {
y = sta.top();
sta.pop();
used[y] = used[i] = true;
ans -= ;
} int have_2 = , have_3 = ;
for (int i = ; i <= n; i++) {
if (used[i])
continue;
switch (c[i]) {
case :
if (have_3)
have_3--, ans--;
else if (have_2)
have_2--, ans--;
break;
case :
if (have_3)
have_3--, have_2++, ans--;
break;
case -:
have_2++;
break;
case -:
have_3++;
break;
}
}
printf("%d\n", ans);
} int main() {
init();
solve();
return ;
}