[题目链接]
[算法]
对于每组询问 , 首先二分答案
显然 , 最优策略为优先选择价格低的
建立可持久化线段树 , 简单维护即可
时间复杂度 : O(NlogN ^ 2)
[代码]
- #include<bits/stdc++.h>
- using namespace std;
- #define N 100010
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- struct info
- {
- int d , p , l;
- } a[N];
- int n , m , len;
- int b[N] , rt[N];
- struct Presitent_Segment_Tree
- {
- int sz;
- Presitent_Segment_Tree()
- {
- sz = 0;
- }
- struct node
- {
- int lc , rc;
- ll cnt , sum;
- } a[N * 40];
- inline void build(int &now , int l , int r)
- {
- now = ++sz;
- if (l == r) return;
- int mid = (l + r)>> 1;
- build(a[now].lc , l , mid);
- build(a[now].rc , mid + 1 , r);
- }
- inline void modify(int &now , int old , int l , int r , int x , int y)
- {
- now = ++sz;
- a[now].lc = a[old].lc , a[now].rc = a[old].rc;
- a[now].cnt = a[old].cnt + y;
- a[now].sum = a[old].sum + 1ll * b[x] * y;
- if (l == r) return;
- int mid = (l + r)>> 1;
- if (mid>= x) modify(a[now].lc , a[now].lc , l , mid , x , y);
- else modify(a[now].rc , a[now].rc , mid + 1 , r , x , y);
- }
- inline ll query(int now , int l , int r , ll x)
- {
- if (l == r)
- return 1ll * b[l] * x;
- int mid = (l + r)>> 1;
- if (a[a[now].lc].cnt>= x) return query(a[now].lc , l , mid , x);
- else return a[a[now].lc].sum + query(a[now].rc , mid + 1 , r , x - a[a[now].lc].cnt);
- }
- } PST;
- template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
- template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
- template <typename T> inline void read(T &x)
- {
- T f = 1; x = 0;
- char c = getchar();
- for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
- for (; isdigit(c); c = getchar()) x = (x <<3) + (x << 1) + c - '0';
- x *= f;
- }
- inline bool cmp(info a , info b)
- {
- return a.d> b.d;
- }
- int main()
- {
- read(n); read(m);
- for (int i = 1; i <= n; i++)
- {
- read(a[i].d);
- read(a[i].p);
- read(a[i].l);
- b[i] = a[i].p;
- }
- sort(b + 1 , b + n + 1);
- len = unique(b + 1 , b + n + 1) - b - 1;
- sort(a + 1 , a + n + 1 , cmp);
- for (int i = 1; i <= n; i++) a[i].p = lower_bound(b + 1 , b + len + 1 , a[i].p) - b;
- PST.build(rt[0] , 1 , len);
- for (int i = 1; i <= n; i++) PST.modify(rt[i] , rt[i - 1] , 1 , len , a[i].p , a[i].l);
- while (m--)
- {
- ll G , L;
- read(G); read(L);
- int l = 0 , r = (int)1e5 , ans = 0;
- while (l <= r)
- {
- int mid = (l + r)>> 1;
- int ll = 1 , rr = n , loc = 0;
- while (ll <= rr)
- {
- int md = (ll + rr)>> 1;
- if (a[md].d>= mid)
- {
- ll = md + 1;
- loc = md;
- } else rr = md - 1;
- }
- if (PST.a[rt[loc]].cnt>= L && PST.query(rt[loc] , 1 , len , L) <= G)
- {
- l = mid + 1;
- ans = mid;
- } else r = mid - 1;
- }
- if (ans == 0) puts("-1");
- else printf("%d\n" , ans);
- }
- return 0;
- }
[CTSC 2018] 混合果汁
来源: http://www.bubuko.com/infodetail-2988888.html