Problem B. Market(market.c/cpp/pas)
Time limit: 1 seconds
Memory limit: 128 megabytes
在比特镇一共有 n 家商店,编号依次为 1 到 n。每家商店只会卖一种物品,其中第 i 家商店的物品单价为 ci,价值为 vi,且该商店开张的时间为 ti。Byteasar计划进行m次购物,其中第i次购物的时间为Ti,预算为Mi。每次购物的时候,Byteasar会在每家商店购买最多一件物品,当然他也可以选择什么都不买。如果购物的时间早于商店开张的时间,那么显然他无法在这家商店进行购物。现在 Byteasar 想知道,对于每个计划,他最多能购入总价值多少的物品。请写一个程序,帮助Byteasar 合理安排购物计划。
注意:每次所花金额不得超过预算,预算也不一定要花完,同时预算不能留给其它计划使用。
Input
第一行包含两个正整数 n;m,表示商店的总数和计划购物的次数。
接下来 n 行,每行三个正整数 ci; vi; ti,分别表示每家商店的单价、价值以及开张时间。
接下来 m 行,每行两个正整数 Ti;Mi,分别表示每个购物计划的时间和预算。
Output
输出 m 行,每行一个整数,对于每个计划输出最大可能的价值和。
Examples
market.in
5 2
5 5 4
1 3 1
3 4 3
6 2 2
4 3 2
3 8
5 9
market.out
10
12
第一个计划可以在商店 2,3,5 各购买一件物品,总花费为 1 + 3 + 4 = 8,总价值为 3 + 4 + 3 = 10。
第二个计划可以在商店 1,2,3 各购买一件物品,总花费为 5 + 1 + 3 = 9,总价值为 5 + 3 + 4 = 12。
解析:
动规;
因为正向的想法无法实现。所以反向思考。令f[i]为装了i的总价值时用的最少的钱;
将商店与问题的T按从小到大排序,这样的话就能简化运算的速度;
f[i]最后要与i之后的进行比较,取最小值;
进行二分;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rint register int inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)) f=(ch==),ch=getchar();
while( isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=getchar();
return f?(~x+):x;
} #define man 330 struct mono{ int val,w,t;}a[man<<];
struct obj{ int t,m,id;}b[]; int cmp(mono a,mono b){
return a.t<b.t;
} int ccmp(obj a,obj b){
return a.t<b.t;
} int n,m,tot,f[],ans[];
const int inf=1e9+; inline void dp(int val,int w){
for(rint i=tot;i>=val;i--) f[i]=min(f[i],f[i-val]+w);
for(rint i=tot-;i>;i--) f[i]=min(f[i],f[i+]);
} inline int search(int w){
int l=,r=tot,mid,ans;
while(l<=r){
mid=(l+r)>>;
if(f[mid]<=w) ans=mid,l=mid+;
else r=mid-;
}
return ans;
} int main(){ freopen("market.in","r",stdin);
freopen("market.out","w",stdout); n=read();m=read();tot=n*;
for(rint i=;i<=n;i++) a[i].w=read(),a[i].val=read(),a[i].t=read();
for(rint i=;i<=m;i++) b[i].t=read(),b[i].m=read(),b[i].id=i; sort(a+,a++n,cmp);
sort(b+,b++m,ccmp); for(rint i=;i<=tot;i++) f[i]=inf;
for(rint i=,j=;i<=m;i++){
while(j<=n&&a[j].t<=b[i].t) dp(a[j].val,a[j].w),j++;
ans[b[i].id]=search(b[i].m);
} for(rint i=;i<=m;i++)
printf("%d\n",ans[i]);
return ;
}
Problem B. Market(market.c/cpp/pas)的更多相关文章
-
模拟赛 Problem 2 不等数列(num.cpp/c/pas)
Problem 2 不等数列(num.cpp/c/pas) [题目描述] 将1到n任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”.问在所有排列中,有多少个排列恰好有 ...
-
模拟赛 Problem 1 高级打字机(type.cpp/c/pas)
Problem 1 高级打字机(type.cpp/c/pas) [题目描述] 早苗入手了最新的高级打字机.最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧. 请为这种高级打字机设计一个程序 ...
-
公路建设 (highway.c/cpp/pas)
2.公路建设 (highway.c/cpp/pas) 在滨海市一共有 n 个城市,编号依次为 1 到 n,它们之间计划修建 m 条双向道路,其中 修建第 i 条道路的费用为 ci. 海霸王作为滨海市公 ...
-
商店购物 (shopping.c/cpp/pas)
1.商店购物 (shopping.c/cpp/pas) 在滨海市开着 n 家商店,编号依次为 1 到 n,其中编号为 1 到 m 的商店有日消费量上 限,第 i 家商店的日消费量上限为 wi. 海霸王 ...
-
基站选址(base.c/cpp/pas)
基站选址(base.c/cpp/pas) 题目描述 有N个村庄坐落在一条直线上,第i(i>1)个村庄距离第1个村庄的距离为Di.需要在这些村庄中建立不超过K个通讯基站,在第i个村庄建立基站的费 ...
-
Problem 1 珠江夜游 (cruise .cpp)———2019.10.6
Problem 1 珠江夜游 (cruise.cpp)[题目描述]小 Z 放假后难得来一趟广州游玩,当然要吃遍广州各路美食小吃然后再到珠江新城看看远近闻名的小蛮腰啦!可当小 Z 一路吃吃吃以后,天渐渐 ...
-
Problem 2 旅行计划 (travelling .cpp)———2019.10.6
lth tql,lzpclxf tql Orz Problem 2 旅行计划 (travelling.cpp)[题目描述]小 Z 打算趁着暑假,开启他的旅行计划.但与其他同学不同的是,小 Z 旅行时并 ...
-
YZOI Easy Round 2_化简(simplify.c/cpp/pas)
Description 给定一个多项式,输出其化简后的结果. Input 一个字符串,只含有关于字母x 的多项式,不含括号与分式,没有多余的空格. Output 一个字符串,化简后的多项式,按照次数从 ...
-
bzoj 3657 斐波那契数列(fib.cpp/pas/c/in/out)
空间 512M 时限2s [题目描述] 有n个大于1的正整数a1,a2,…,an,我们知道斐波那契数列的递推式是f(i)=f(i-1)+f(i-2),现在我们修改这个递推式变为f(i)=f(i-1) ...
随机推荐
-
你用过这种奇葩的C#注释吗?如何看待
本人虽然不是专业开发人员,也非专业出身,但一直使用C#堆码,解决自己日常的小问题.包括自己的研究,也是用C#来实现和测试.对C#是情有独钟.虽然C#的很多高级技术不会用,也不太懂,但总归是知道,耳闻目 ...
-
c#.net 使用NPOI导入导出标准Excel (asp.net winform csharp)
尝试过很多Excel导入导出方法,都不太理想,无意中逛到oschina时,发现了NPOI,无需Office COM组件且不依赖Office,顿时惊为天人,怀着无比激动的心情写下此文. 曾使用过的方法 ...
-
jquery实现div遮罩层
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...
-
RabbitMQ介绍5 - 集群
RabbitMQ内建集群机制,利用Erlang提供的开放电信平台(OTP,Open telecom Platform)通信框架,使得集群很容易进行横向扩展,提高系统吞吐量.这里只讨论集群的概念.原理, ...
-
部署新浪SAE web.py Session及图片上传等问题注意事项
1.以下几条代码解决编码问题 import sysreload(sys)sys.setdefaultencoding('utf-8') 2.图片上传问题 需要开通sina的Storage服务,随便建个 ...
-
微生物增殖|2012年蓝桥杯B组题解析第一题-fishers
(3')微生物增殖 假设有两种微生物 X 和 Y X出生后每隔3分钟分裂一次(数目加倍),Y出生后每隔2分钟分裂一次(数目加倍). 一个新出生的X,半分钟之后吃掉1个Y,并且,从此开始,每隔1分钟吃1 ...
-
统计学习方法c++实现之二 k近邻法
统计学习方法c++实现之二 k近邻算法 前言 k近邻算法可以说概念上很简单,即:"给定一个训练数据集,对新的输入实例,在训练数据集中找到与这个实例最邻近的k个实例,这k个实例的多数属于某个类 ...
-
uva1366 dp
这题说的是给了 一个矩阵在每个单元内有BLOHHLUM 种的资源 Bi,j, 有YEYENUM 种的 资源Ai,j , 资 源 从 该 单 位 出 发 不能 转 弯 直 接 运 送 到 像 B 类 资 ...
-
FTP在docker容器中上传失败解决,改为被动模式
package com.mayocase.takeout.utils; import org.apache.commons.net.ftp.FTPClient; import org.apache.c ...
-
用C#实现通过串口对设备的数据采集--Server层
今天中午没睡午觉,头昏眼花的,实在写不了代码,把这几天写的Server层数据采集的程序整理了一下. WatrLevelDataCollectServer.cs using System; using ...