P7990 code

lsj2009 · 2021-12-24 21:23:48 · 题解

更好的阅读体验。

赛时看见这题一眼：什么鬼！然后马上去 T2，结果回过头来 30minAC。

现在看是绿很河狸。。。

思路

很明显，这是一道贪心，那么该怎么贪呢？仔细琢磨样例之后发现一种方法：

首先，求出对每块草地与其最近的 FN 的距离，装入 dis[] 数组，那么则对于草地 i 而言，只有 FJ 将奶牛放在其方圆 dis_i 内（不含），才能占据此草地。

那么，我们对于经典的区间选点问题，我们可知，FJ在考虑 i 号草地时，将奶牛放在 p_i\pm(dis_i-1) 处最优。

我们可以将 FJ 在某地可以放一头奶牛可以占领的草地看做一块“草地”，则最后将“草地”按 t_i 降序排序，ans=\sum_{i=1}^{n} t_i。

更多细节详见代码。

AC CODE：

#include<bits/stdc++.h>
#define pd push_back
#define int long long //十年OI一场空，不开longlong见祖宗
using namespace std;
const int N=2e5+5;
int f[N],d[N],n,m,k,tot;
struct grass {
    int p,t;
    bool operator < (const grass& x) const {
        return p<x.p;
    }
}; grass a[N];
bool cmp(const grass& x,const grass& y) { //草地最后ti降序
    return x.t>y.t;
}
signed main() {
    scanf("%lld%lld%lld",&k,&m,&n);
    for(int i=1;i<=k;i++)
        scanf("%lld%lld",&a[i].p,&a[i].t);
    for(int i=1;i<=m;i++)
        scanf("%lld",&f[i]);
    sort(f+1,f+m+1); sort(a+1,a+k+1);
    memset(d,0x7f,sizeof(d)); //处理dis数组
    for(int i=1;i<=k;i++) {
        int x=lower_bound(f+1,f+m+1,a[i].p)-f;
        if(x!=m+1) d[i]=min(d[i],f[x]-a[i].p);
        if(x!=1) d[i]=min(d[i],a[i].p-f[x-1]);
    }
//  for(int i=1;i<=k;i++)
//      printf("%lld'min_dis = %lld\n",i,d[i]);
    vector<grass> ans;
    ans.pd(grass{a[1].p+d[1]-1,a[1].t}); //一号草地可以覆盖的最远点和当前美味值
    for(int i=2;i<=k;i++)
        if(a[i].p-d[i]<ans.back().p) { //当前草地可以和i号草地“共处一室”
            grass tmp=ans.back(); ans.pop_back(); ans.pd(grass{tmp.p,tmp.t+a[i].t});
        } else //另外开辟草地
            ans.pd(grass{a[i].p+d[i]-1,a[i].t});
    sort(ans.begin(),ans.end(),cmp);
    int tot=0;
    for(int i=0;i<n;i++) //累加前n值
        tot+=ans[i].t;
    printf("%lld",tot);
    return 1;
}