bzoj 2794 [Poi2012]Cloakroom 离线+背包

题目大意

有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]<b[i])。

再给出q个询问，每个询问由非负整数m, k, s组成，问是否能够选出某些物品使得：

对于每个选的物品i，满足a[i]<=m且b[i]>m+s。
所有选出物品的c[i]的和正好是k。

第一行一个正整数\(n (n\le 1,000\))，接下来n行每行三个正整数，分别表示c[i], a[i], b[i] (\(c[i]\le 1,000, 1\le a[i]<b[i]\le 10^9\))。

下面一行一个正整数\(q (q\le 1,000,000\))，接下来\(q\)行每行三个非负整数\(m, k, s (1\le m\le 10^9, 1\le k\le 100,000, 0\le s\le 10^9)\)。

分析

离线后将a,m快排

背包一下求出每种c需要的最小的b最大是多少

O(快排+n*k)

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

const int N=1007;

const int M=1000007;

const int V=100007;

const int INF=2147483647;

inline int rd(){

    int x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

    for(;isdigit(c);c=getchar()) x=x*10+c-48;

    return f?x:-x;

}

int n,m;

int ans[M];

struct node{

    int a,b,c,id;

    node(int aa=0,int bb=0,int cc=0,int ii=0){a=aa;b=bb;c=cc;id=ii;}

}a[N],q[M];

bool cmpa(node x,node y){return x.a<y.a;}

int f[V];

void in(int w,int bb){

    for(int i=V-1;i>=w;i--)

    if(f[i-w]) f[i]=max(f[i],min(f[i-w],bb));

}

int main(){

    int i,j,x,y,z;

    n=rd();

    for(i=1;i<=n;i++){

        z=rd(),x=rd(),y=rd();

        a[i]=node(x,y,z);

    }

    m=rd();

    for(i=1;i<=m;i++){

        x=rd(),z=rd(),y=x+rd()+1;

        q[i]=node(x,y,z,i);

    }

    sort(a+1,a+n+1,cmpa);

    sort(q+1,q+m+1,cmpa);

    f[0]=INF;

    for(j=1,i=1;i<=m;i++){

        for(;j<=n&&a[j].a<=q[i].a;j++) in(a[j].c,a[j].b);

        ans[q[i].id]=q[i].b<=f[q[i].c];

    }

    for(i=1;i<=m;i++) puts(ans[i]?"TAK":"NIE");  

    return 0;

}

巴特西

bzoj 2794 [Poi2012]Cloakroom 离线+背包

题目大意

分析

solution

最新文章

热门文章