Earth Wind and Fire
题意
给两个长度为 $n$ 个数组 $a,b$, 如果 $a_ile a_j$ 可以取一个 $d(0le 2*dle a_j-a_i)$ , 然后 $a_i+d,a_j-d$ , 问如何操作可以让 $a$ 变为 $b$
题解
对 $a,b$ 排序, 将 $a_i$ 变为 $b_i$, 用一个 $stack$ 维护 $a$ 中待加值的元素
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
pii a[N];
int b[N];
bool (pii x,pii y){
return x.fi<y.fi;
}
struct da{
int i,j,d;
da(int q,int w,int e){
i=q;j=w;d=e;
}
};
vector<da>v;
stack<int>les;
int main() {
int n;
in(n);
for1(i,n){
in(a[i].fi);
a[i].se=i;
}
for1(i,n)in(b[i]);
sort(a+1,a+1+n,cmp);
sort(b+1,b+n+1);
bool yes=1;
for1(i,n){
if(a[i].fi>b[i]){
a[i].fi-=b[i];
while(a[i].fi&&les.size()){
int no=les.top();
les.pop();
int minn=min(a[no].fi,a[i].fi);
if(a[no].fi>a[i].fi)les.push(no);
a[i].fi-=minn;
a[no].fi-=minn;
v.pu_b(da(a[no].se,a[i].se,minn));
}
if(a[i].fi){
yes=0;
break;
}
}else if(a[i].fi<b[i]){
a[i].fi=b[i]-a[i].fi;
les.push(i);
}
}
if(les.size()==0&&yes){
puts("YES");
assert(v.size()<=5*n);
outln((int)v.size());
for(auto i:v){
printf("%d %d %dn",i.i,i.j,i.d);
}
}else
{
puts("NO");
}
return 0;
}
|
近期评论