BZOJ 3703: 昊昊的壮举之造福社会

传送门

搜索，剪枝

首先可以二分答案迭代加深，假设要买 $p$ 台

那么肯定卖价格最小的 $p$ 台

再来个 $A*$ ，设搜到当前情况时，有 $waste$ 的钱一定要被浪费（其实就是某些学校剩下的钱连最便宜的都买不起）

设最便宜的 $p$ 台电脑总价值为 $sum$ ，所有学校的总钱数为 $S$，那么我们最多浪费 $S-tot$，如果 $waste>S-tot$ 就直接返回

但是显然还是不够

看看数据发现相同价格的电脑和相同初始钱数的学校数量很多

不妨使搜索时保证，对于相同价格的电脑，购买的学校的初始钱数单调不增，显然这样不会影响搜索时的正确性

然后就可以跑过了

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=5e5+;

int n,m,mon[N],cst[N],ans;

int S,sum[N],Mx,Las[N];

bool GG;

void dfs(int pos,int waste)

{

    if(waste>Mx) return;

    if(!pos) { GG=; return; }

    int R=Las[cst[pos]];

    for(int i=R;i;i--)

    {

        if(cst[pos]>mon[i]) continue;

        mon[i]-=cst[pos]; Las[cst[pos]]=i;

        dfs(pos-,waste+ (mon[i]<cst[])*mon[i] );

        mon[i]+=cst[pos];

        if(GG) return;//记得先还原mon再返回

    }

    Las[cst[pos]]=R;

}

bool check(int p)

{

    if(sum[p]>S||cst[p]>mon[m]) return ;

    GG=; Mx=S-sum[p];

    for(int i=;i<=n;i++) Las[cst[i]]=m;//每次都要初始化Las

    dfs(p,); return GG;

}

int main()

{

    m=read();

    for(int i=;i<=m;i++) mon[i]=read(),S+=mon[i];

    n=read();

    for(int i=;i<=n;i++) cst[i]=read();

    sort(mon+,mon+m+); sort(cst+,cst+n+);

    for(int i=;i<=n;i++) sum[i]=sum[i-]+cst[i];

    int L=,R=n;

    while(L<=R)

    {

        int mid=L+R>>;

        if(check(mid)) L=mid+,ans=mid;

        else R=mid-;

    }

    printf("%d\n",ans);

    return ;

}

巴特西

BZOJ 3703: 昊昊的壮举之造福社会

最新文章

热门文章