柳州建设厅官方网站,wordpress图片自动分页插件下载,百度app下载,制作网站程序正题
题目链接:http://noip.ybtoj.com.cn/contest/105/problem/1 题目大意 nnn个物品#xff0c;每个价格为viv_ivi有xix_ixi个#xff0c;mmm次#xff0c;开始有wiw_iwi元。每次选择能买的最贵的买#xff0c;求能买多少。 解题思路
分两种情况讨论#xff0c;如…正题
题目链接:http://noip.ybtoj.com.cn/contest/105/problem/1 题目大意
nnn个物品每个价格为viv_ivi有xix_ixi个mmm次开始有wiw_iwi元。每次选择能买的最贵的买求能买多少。 解题思路
分两种情况讨论如果wi≥xnoww_i\geq x_{now}wi≥xnow那么就二分出一个位置使得买到这里后不能再买了然后nownownow跳过去。如果wixnoww_i x_{now}wixnow那么二分出一个位置使得wi≥xnoww_i\geq x_{now}wi≥xnow然后nownownow跳过去。
这样每次wiw_iwi会减少一半所以时间复杂度是O(qlogwilogn)O(q\log w_i\log n)O(qlogwilogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
struct node{ll v,x;
}a[N];
ll n,m,b[N],s[N],k[N];
bool cmp(node x,node y)
{return x.vy.v;}
int main()
{freopen(present.in,r,stdin);freopen(present.out,w,stdout);scanf(%lld%lld,n,m);for(ll i1;in;i)scanf(%lld%lld,a[i].v,a[i].x);sort(a1,a1n,cmp);for(ll i1;in;i)b[i]b[i-1]a[i].v*a[i].x,s[i]s[i-1]a[i].x,k[n-i1]a[i].v;while(m--){ll q,ans0,x0;scanf(%lld,q);while(xnq){if(qa[x1].v){ll ylower_bound(bx1,b1n,qb[x])-b;if(yx)break;anss[y-1]-s[x];q-b[y-1]-b[x];xy;if(xn)break;ansq/a[x].v;q%a[x].v;}else{ll yupper_bound(k1,k1n,q)-k-1;if(!y)break;xn-y;}}printf(%lld\n,ans);}
}
