出题人题解 | #Tachibana Kanade Loves Sequence#

原题解链接：https://ac.nowcoder.com/discuss/173818

简单的贪心题。最后一个测试点专门卡了一下$n=0n=0$可能让部分dalao的体验极差……出题人在此谢罪qwq

题目的含义其实是可以从$\{a\},\{b\}\backslash \{a\backslash \},\; \backslash \{b\backslash \}$中选出若干个数，选择一个数代价为$11$，你的利益为你$\{a\}\backslash \{a\backslash \}$和$\{b\}\backslash \{b\backslash \}$利益中的最小值。最大化你的利益。

我们记$A={\sum }_{i=1}^n{a}_i{c}_i,B={\sum }_{i=1}^n{b}_i{d}_i,K={\sum }_{i=1}^n{c}_i+{\sum }_{i=1}^n{d}_{i}A=\backslash sum^n\_\{i=1\}\; a\_ic\_i,\; B=\backslash sum^n\_\{i=1\}\; b\_id\_i,\; K=\backslash sum^n\_\{i=1\}\; c\_i\; +\; \backslash sum^n\_\{i=1\}\; d\_i$ ，答案为$\min \{A,B\}-C\backslash min\backslash \{A,B\backslash \}-C$

一个显然的贪心策略，是将两个序列从大到小排序，然后考虑$A,BA,B$中较小的那一个，从它所对应的序列$\mathrm{（}A\mathrm{对}\mathrm{应}{a}_i\mathrm{},B\mathrm{对}\mathrm{应}{b}_i\mathrm{}\mathrm{）}（A对应a\_i\; \; ,B对应b\_i\; \; ）$中选出最大的没有被选的一个数，将它选中，直到我们找不到一个大于$11$的数。

下面我们来考虑这种贪心的正确性。假设我们在$\{a_i\}\backslash \{a\_i\backslash \}$中选择了$k_{1}k\_1$个数$a_{i_1},a_{i_2},\cdots ,a_{i_{k_1}}a\_\{i\_1\},\; a\_\{i\_2\},\backslash cdots,\; a\_\{i\_\{k\_1\}\}$，$\{b_i\}\backslash \{b\_i\backslash \}$中选择了$k_{2}k\_2$个数$b_{j_1},b_{j_2},\cdots ,b_{j_{k_2}}b\_\{j\_1\},\; b\_\{j\_2\},\; \backslash cdots,\; b\_\{j\_\{k\_2\}\}$，记这种取数方案为$G(I,J)G(I,J)$，其中$I=\{i_1,i_2,\cdots ,i_{k_1}\},J=\{j_1,j_2,\cdots ,j_{k_2}\}I=\backslash \{i\_1,i\_2,\backslash cdots,i\_\{k\_1\}\backslash \},\; J=\backslash \{j\_1,j\_2,\backslash cdots,j\_\{k\_2\}\backslash \}$。由于$\{a_i\}\mathrm{，}\{b_i\}\backslash \{a\_i\backslash \}，\backslash \{b\_i\backslash \}$地位均等，因此我们不妨设$A>BA>B$。

假设另有一种取数方案$G^{\mathrm{\prime }}(I^{\mathrm{\prime }},J^{\mathrm{\prime }})G\text{'}(I\text{'},J\text{'})$比$GG$更优，则显然有$I^{\mathrm{\prime }}\subset I,J^{\mathrm{\prime }}\subset JI\text{'}\backslash subset\; I,\; J\text{'}\; \backslash subset\; J$。为什么？若存在一个下标$jj$，使得$j\in J^{\mathrm{\prime }}j\backslash in\; J\text{'}$ 且$j\mathrm{\notin }Jj\backslash notin\; J$，则其一定选择了一个$JJ$中没有的$jj$，使得$b_j-1>0b\_j\; -\; 1>0$，这与我们在选取中“直到我们找不到一个大于$11$的数”矛盾。同理，可证$I^{\mathrm{\prime }}\subset II\text{'}\; \backslash subset\; I$

那么，由上可得，$G^{\mathrm{\prime }}(I^{\mathrm{\prime }},J^{\mathrm{\prime }})G\text{'}(I\text{'},\; J\text{'})$对应的方案，一定是从$G(I,J)G(I,J)$对应的方案中，将一些选择的数删去，使得答案更优。

1. 若删去$JJ$中的某个数$b_{j}b\_j$ 则会使$KK$减少$11$，$\min A,B\backslash min\; \{A,B\}$减少$b_{j}b\_j$，答案会增 加$1-b_{j}1-b\_j$ ，但根据我们的取数方案，$b_j>1b\_j\; >\; 1$，因此答案会变得更差，与$G^{\mathrm{\prime }}G\text{'}$更优矛盾

2. 若删去$II$中的某个数$a_{i}a\_i$ 则会使$KK$减少$11$，$AA$减少$a_{i}a\_i$。根据我们的取数方案，我们每次都是从最小的收益对应的序列中选择的数，删去$a_{i}a\_i$后，不可能有$A>BA>B$。为什么？考虑到我们从大到小选取$\{a_i\}\backslash \{a\_i\backslash \}$中的每一个数，且当且仅当$A⩽BA\backslash leqslant\; B$时，才会选择$\{a_i\}\backslash \{a\_i\backslash \}$中的数。显然，若删去$a_{i}a\_i$后$A>BA>B$，则我们不可能选择$\{a_i\}\backslash \{a\_i\backslash \}$中的数，更不可能选择$a_{i}a\_i$。因此，必有。但考虑到我们选取时，序列中均为整数，因此显然有$A⩽B-1A\; \backslash leqslant\; B-1$，这使得$\min A,B\backslash min\; \{A,B\}$至少减少了$11$，因此答案反而至少减少了$00$，因此答案不会变得更优。

综上，我们的贪心策略时正确的。

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define F2(i,a,b) for(int i=a;i<(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define MN 6000005
#define ll long long
int n,m,q,k;
int a[MN],b[MN],ap[MN],bp[MN];
int h[MN];
ll ans=0,ii=1,jj=1;
int main(){
    scanf("%d",&n);
    F(i,1,n)scanf("%d",a+i),ap[i]=i;
    F(i,1,n)scanf("%d",b+i),bp[i]=i;
    sort(ap+1,ap+n+1,[](int i,int j){return a[i]>a[j];});
    sort(bp+1,bp+n+1,[](int i,int j){return b[i]>b[j];});
    int i=1,j=1;
    ll s1=0,s2=0;
    while(i<=n||j<=n){
        int s;
        if(i<=n&&j<=n)s=s2<s1;
        else s=j<=n;
        if(s)s2+=b[bp[j++]];
        else s1+=a[ap[i++]];
        if(ans<min(s1,s2)-i-j+2)
            ans=min(s1,s2)-i-j+2,ii=i,jj=j;
    }printf("%lld\n",ans);
    F2(i,1,ii)h[ap[i]]=1;
    F(i,1,n)printf("%d ",h[i]);puts("");
    F(i,1,n)h[i]=0;
    F2(i,1,jj)h[bp[i]]=1;
    F(i,1,n)printf("%d ",h[i]);
    return 0;
}