题目描述
有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]<b[i])。
再给出q个询问，每个询问由非负整数m, k, s组成，问是否能够选出某些物品使得：
1. 对于每个选的物品i，满足a[i]<=m且b[i]>m+s。
2. 所有选出物品的c[i]的和正好是k。
输入
第一行一个正整数n (n<=1,000)，接下来n行每行三个正整数，分别表示c[i], a[i], b[i] (c[i]<=1,000, 1<=a[i]<b[i]<=10^9)。
下面一行一个正整数q (q<=1,000,000)，接下来q行每行三个非负整数m, k, s (1<=m<=10^9, 1<=k<=100,000, 0<=s<=10^9)。
输出
输出q行，每行为TAK (yes)或NIE (no)，第i行对应第i此询问的答案。
样例输入
5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5
样例输出
TAK
NIE
TAK
TAK
NIE
NIE
TAK
TAK
NIE
发现在线回答每个询问时间复杂度较高，因此考虑离线。
将所有物品按a排序，所有询问按m排序。设f[i]表示物品c的和为i时选取的b的最小值最大是多少。
按顺序选取物品进行01背包转移。
对于每个询问只要判断f[k]是否>=s+m就好了。
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int a;
int b;
int c;
int id;
}x[1010],y[1200000];
int f[100010];
int ans[1200000];
bool cmp(node x,node y)
{
return x.a<y.a;
}
int n,m;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x[i].c,&x[i].a,&x[i].b);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&y[i].a,&y[i].b,&y[i].c);
y[i].id=i;
}
sort(x+1,x+n+1,cmp);
sort(y+1,y+m+1,cmp);
int num=1;
f[0]=1e9;
for(int i=1;i<=m;i++)
{
while(num<=n&&x[num].a<=y[i].a)
{
for(int k=100000;k>=x[num].c;--k)
{
f[k]=max(f[k],min(f[k-x[num].c],x[num].b));
}
num++;
}
if(f[y[i].b]>y[i].a+y[i].c)
{
ans[y[i].id]=1;
}
}
for(int i=1;i<=m;i++)
{
ans[i]?printf("TAK\n"):printf("NIE\n");
}
}