2018.08.22 NOIP模拟 shop(lower_bound+前缀和预处理)
2024-09-13 21:58:15
Shop
有 n 种物品,第 i 种物品的价格为 vi,每天最多购买 xi 个。
有 m 天,第 i 天你有 wi 的钱,你会不停购买能买得起的最贵的物品。你需要求出你每天会购买多少个物品。
【输入格式】
第一行两个整数 n,m。接下来 n 行每行两个整数 vi,xi。接下来 m 行每行一个整数
wi
【输出格式】
m 行每行一个整数,第 i 行表示第 i 天购买的物品数量。
【输入样例】
3 3
1 1
2 2
3 3
5
10
15
【输出样例】
2
4
6
【数据规模】
对于 20%的数据,n,m<=1000。
对于另外 40%的数据,xi=1。
对于 100%的数据,n,m<=100000,1<=vi<=10^9,1<=xi<=10000,0<=wi<=10^18。
考试唯一A掉的题。。。
预处理出从大到小的后缀和,先查询出最前面能买多少,买完之后有一个性质是之后每买一种商品剩下的钱至少减去一半。
这样的话只需要logw次lower_bound查询就行了。
代码:
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void write(ll x){
if(x>9)write(x/10);
putchar((x%10)^48);
}
int n,m;
ll sum[N],a[N],b[N],num[N];
struct Node{ll v,x;}p[N];
inline bool cmp(Node a,Node b){return a.v<b.v;}
int main(){
freopen("shop.in","r",stdin);
freopen("shop.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i)p[i].v=read(),p[i].x=read();
sort(p+1,p+n+1,cmp);
int tot=0;
for(int i=1;i<=n;++i){
if(p[i].v!=p[i-1].v)p[++tot]=p[i];
else p[tot].x+=p[i].x;
}
n=tot;
sum[n+1]=num[n+1]=0;
for(int i=n;i;--i)sum[i]=sum[i+1]+p[i].x*p[i].v,a[n-i+1]=sum[i],b[i]=p[i].v,num[i]=num[i+1]+p[i].x;
while(m--){
ll w=read(),ans=0;
int pos=n-(lower_bound(a+1,a+n+1,w)-a)+2;
w-=sum[pos],ans+=num[pos],--pos;
while(pos>=1&&w>=p[1].v){
int ppos=pos;
pos=lower_bound(b+1,b+pos+1,w)-b;
if((p[pos].v>w)||pos>ppos)--pos;
if(pos<1)break;
ll tmp=min(p[pos].x,w/p[pos].v);
w-=p[pos].v*tmp,ans+=tmp;
--pos;
}
write(ans),puts("");
}
return 0;
}
最新文章
- 【.net 深呼吸】记录WCF的通信消息
- MongoDB学习笔记~为IMongoRepository接口更新指定字段
- 很不错的sql练习题(select)
- Windows Azure Active Directory (2) Windows Azure AD基础
- java 驼峰字符和下划线字符相互转换工具类
- AJAX原理及XMLHttpRequest对象分析
- ORACLE 数据块dump
- FZU 2093 找兔子 状压DP
- C# HttpRequest 中文编码问题
- JavaScript显示分页按钮
- C#的垃圾回收机制及弱引用
- java_设计模式_适配器模式_Adapter Pattern(2016-08-09)
- 《Spring敲门砖之基础教程第一季》 第一章 概要介绍
- hibernate学习(二)
- 走进spring之springmvc
- 闲聊cassandra
- JAVA_SE基础——43.抽象类
- Springboot读取本地图片并显示
- Spring学习之旅(一)极速创建Spring框架java工程项目
- 为什么学习Lua