【TEST】【2019.09.15】【market】

                                             购物    market.cpp/1S/256M

【题目描述】

在比特镇一共有n家商店，编号依次为1到n。每家商店只会卖一种物品，其中第i家商店的物品单价为ci，价值为vi，且该商店开张的时间为ti。

Byteasar计划进行m次购物，其中第i次购物的时间为Ti，预算为Mi。每次购物的时候，Byteasar会在每家商店购买最多一件物品，当然他也可以选择什么都不买。如果购物的时间早于商店开张的时间，那么显然他无法在这家商店进行购物。

现在Byteasar想知道，对于每个计划，他最多能购入总价值多少的物品。请写一个程序，帮助Byteasar合理安排购物计划。

注意：每次所花金额不得超过预算，预算也不一定要花完，同时预算不能留给其它计划使用。

【输入文件】

第一行包含两个正整数n，m，表示商店的总数和计划购物的次数。

接下来n行，每行三个正整数ci,vi,ti，分别表示每家商店的单价、价值以及开张时间。

接下来m行，每行两个正整数Ti,Mi，分别表示每个购物计划的时间和预算。

【输出文件】

    输出m行，每行一个整数，对于每个计划输出最大可能的价值和。

【样例输入输出】   

	market.in	market.out
样例1	5 2 5 5 4 1 3 1 3 4 3 6 2 2 4 3 2 3 8  5 9	10 12

第一个计划可以在商店2，3，5各购买一件物品，总花费为1+3+4=8，总价值为3+4+3=10。

第二个计划可以在商店1，2，3各购买一件物品，总花费为5+1+3=9，总价值为5+3+4=12。

【数据规模】

对于 100% 的数据，1<=ti ,Ti<=n。

（打完 才 后知后觉地 发现 把超市 弄成了物品，但是没关系，你懂就好了嘛）

 

对于这道题，看完题目后，01背包应该是先想到的，因为 只有 买一件 或者什么都不买 两种选择。

考虑  60% 的数据：用dp[i][j] 表示 前i件物品 花了j元 所能获得的最大价值

我们发现 前 60% 花费很少 虽然 5、6号点 m （询问） 很大，但是时间只有那么多，所以它一定重复询问了 同一 时间    不同花费下的最大价值   所以，我们就处理出 不同时间下 花了 最多的钱（也只有300） 所能得到的最大价值。最后直接O（1） 回复查询 即可 ，至于担心 会有影响的请自行思考。（方法：排序）还有很多细节：例如：询问的时间会超过最大时间 | 询问的时间不在给出的时间内 等等。

 

考虑 100% 数据 ： 我们会发现：我们时间和空间 受限制于 10^9 的花费，但是 最大价值 只有 300*300 ，因此，我们把dp数组反过来，dp[i][j] 表示 前 i 个物品 价值为 j 元 时的  最小  花费

如何 查询呢 ？

我们先想一想 查询 很少的话，我们 的 朴素 做法：

对于每一个查询，从最大价值 向 最小价值（0） 循环，如果 出现  一个 价值 满足 它需要的花费 小于等于 我 本次拥有的花费，那 它 就是 最大花费 ，输出即可！

正确性是显然的，因为我保证了 价值 一定 是 满足条件的 价值中 最大 的。

但是 TLE 也是显然的。

我们就想着  ： 它会 重复询问 每一个时间 ，（每一个时间会对应一个前 i 件物品 的限制，排序后）我们能不能将它限制至时间范围内呢？

我们先把 查询 按时间从小到大 排序 ，时间相同的 按 花费 从大到小 排序。

我们从 时间 或者说是 物品 从小到大 开始 循环，对于 每一个时间 （物品）的内层 从大到小 循环 价值 ，满足的就储存起来赋值。这就体现了 把时间相同的 按花费 从小到大 排序的 必要性，花费大的（钱多的）得不到 当前这个 价值，花费少的 更得不到了，也就是不用循环来找了，利用单调性 即可。

 

无论哪一种，（按照我的写法）输入的物品 应该按照时间排序，这样 从小到大的时间 就可以和 前 i 件物品对应，保证了 正确性  -- 单调性 --  无后效性 。

（也许数据会有坑---买物品或卖物品的时间从0开始，说好的 大于等于 1 呢，如果WA了一两个点，你可以先改改这些地方，最好看看数据有没有  有的话 再改）

（没懂？代码中也有解释，结合代码 吃透它！！）

100 代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define N 304
#define V 90006
#define TIME 304
#define inf 0x3f3f3f3f
#define M 100007
using namespace std;

inline int wread(){
    char c=getchar ();int flag=1,wans=0;
    while (c<'0'||c>'9'){if (c=='-') flag=-1;c=getchar ();}
    while (c>='0'&&c<='9'){wans=wans*10+c-'0';c=getchar ();}
    return wans*=flag;
}

int n,m;
struct node {int dan,val,tim;}a[N];
int dp[N][V];
int maxtime,maxv;
struct node2 {int tim,mon,hao;}b[M];
bool e666 (node x,node y){return x.tim<y.tim;}
int sav[TIME];//时间为i时对应的个数值 

bool e555 (node2 x,node2 y){
    if (x.tim==y.tim)	return x.mon>y.mon;
    return x.tim<y.tim;
}
int pr[M];
int main (){
	
    n=wread();m=wread();
    for (int i=1;i<=n;++i)
        a[i].dan=wread(),a[i].val=wread(),a[i].tim=wread(),maxtime=max(maxtime,a[i].tim),maxv+=a[i].val;
    sort (a+1,a+n+1,e666);//开业时间排序 
    
    // dp 
	memset (dp,inf,sizeof dp);
    for (int i=0;i<=n;++i)
        dp[i][0]=0;//初始化操作 
        
    for (int i=1;i<=n;++i){
        for (int j=1;j<=maxv;++j){
            if (a[i].val<=j)
                dp[i][j]=min(dp[i-1][j-a[i].val]+a[i].dan,dp[i][j]);
            dp[i][j]=min (dp[i][j],dp[i-1][j]);
        }
    }
    
    
    //对于不同的时间 我应该 找 前 几个物品 
    // sav[i] = y  表示询问 i 时间, 满足要求 (开业时间 <= i) 的 在前 y 个 
    for (int i=1;i<=n;++i){
        int tim=a[i].tim;
        sav[tim]=i;
    }
    //可能会存在 询问时间 不在 开业时间的整点上 的
	// e.g 开业时间有 3 8 105
	//     查询时间有 5 10 300 
    for (int i=1;i<=maxtime;++i)
        if (!sav[i])
            sav[i]=sav[i-1];
     
     
    //询问的离线处理 
    for (int i=1;i<=m;++i){
        int tim=wread(),mon=wread();
        if (tim>maxtime)	tim=maxtime;
        int num=sav[tim];
        b[i].tim=num;b[i].mon=mon,b[i].hao=i;
    }
    sort (b+1,b+m+1,e555);//先按时间从小到大，再按钱数从大到小 
    
    
    int zhi=1;//表示当前在询问的哪一个位置 (询问已经排序) 
    for (int i=0;i<=n;++i){
        if (b[zhi].tim!=i)	continue;
        bool F=true;
        for (int j=maxv;j>=0;--j){
            while (b[zhi].mon>=dp[i][j])	{//记得写循环!! 
                pr[b[zhi].hao]=j,zhi++;	
                if (b[zhi].tim!=i)	{F=false;break;}
            }
            if (!F)	break;
        }
        if (F)		while (b[zhi].tim==i)	zhi++;
    }
    //整体输出答案 
    for (int i=1;i<=m;++i){
        printf("%d\n",pr[i]);
    }
    return 0;
}

滚动数组 100 代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 304
#define V 90006
#define TIME 304
#define inf 0x3f3f3f3f
#define M 100007
using namespace std;

inline int wread(){
    char c=getchar ();int flag=1,wans=0;
    while (c<'0'||c>'9'){if (c=='-') flag=-1;c=getchar ();}
    while (c>='0'&&c<='9'){wans=wans*10+c-'0';c=getchar ();}
    return wans*=flag;
}

int n,m;
struct node {int dan,val,tim;}a[N];
int dp[V];
int maxtime,maxv;
int sav[TIME];//时间为i时对应的个数值 
int pr[M];
struct node2 {int tim,mon,hao;}b[M];

bool e666 (node x,node y){return x.tim<y.tim;}
bool e555 (node2 x,node2 y){
    if (x.tim==y.tim)	return x.mon>y.mon;
    return x.tim<y.tim;
}

int main (){
    n=wread();m=wread();
    for (int i=1;i<=n;++i)
        a[i].dan=wread(),a[i].val=wread(),a[i].tim=wread(),maxtime=max(maxtime,a[i].tim),maxv+=a[i].val;
    sort (a+1,a+n+1,e666);
    
    for (int i=1;i<=n;++i)
        sav[a[i].tim]=i;
    
    for (int i=1;i<=maxtime;++i)
        if (!sav[i])
            sav[i]=sav[i-1];
    
    for (int i=1;i<=m;++i)
        b[i].tim=sav[min(wread(),maxtime)],b[i].mon=wread(),b[i].hao=i;
    
    stable_sort (b+1,b+m+1,e555);//先按时间从小到大，再按钱数从大到小 
    
    memset (dp,inf,sizeof dp);
    int zhi=1;
    for (int i=0;i<=n;++i){
    	dp[0]=0;
        for (int j=maxv;j>=0;--j){
            if (a[i].val<=j)
                dp[j]=min(dp[j-a[i].val]+a[i].dan,dp[j]);
            dp[j]=min (dp[j],dp[j]);
        }
        if (b[zhi].tim!=i)	continue;
        bool F=true;
        for (int j=maxv;j>=0;--j){
            while (b[zhi].mon>=dp[j])	{
                pr[b[zhi].hao]=j,zhi++;	
                if (b[zhi].tim!=i)	{F=false;break;}
            }
            if (!F)	break;
        }
        if (F)		while (b[zhi].tim==i)	zhi++;
    }
    
    for (int i=1;i<=m;++i)
        printf("%d\n",pr[i]);
    return 0;
}