CF-1148E

Posted on | Edited on | In | Views:

Earth Wind and Fire

题意

给两个长度为 $n$ 个数组 $a,b$, 如果 $a_i\le a_j$ 可以取一个 $d(0\le 2*d\le 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 cmp(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 %d\n",i.i,i.j,i.d);
        }
    }else
    {
        puts("NO");
    }
    return 0;
}