我不会贪心。
\(a\) 元的物品有 \(b\) 元的折扣，就相当于 \(a\) 元的物品有一张 \(a-b\) 元的优惠券。
因为一张优惠券是满 \(w\) 元才可以用，所以可以用的物品在价格 \(a\) 上是一段区间 \([a,\inf]\)。
有一个很朴素的想法是，将每一个物品最多能省多少钱先弄出来，然后用优惠券想办法把省的最小的钱换成优惠券。
先将物品和优惠券按满多少可以有优惠排序，再枚举优惠券，最后就是按照上面说的逐步加进去就好了。
想要快速求出最小值可以用优先队列，如果到最后还用不到优惠券的记得把打得折加进去。
时间复杂度 \(O(n \log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int ll
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();
#define ll long long
#define i128 __int128
using namespace std;
inline int read() {
int xx= 0;int f= 1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f= -1;
c= getchar();
}
while(c>='0'&&c<='9') {
xx= (xx<<1)+(xx<<3)+(c^48);
c= getchar();
}
return xx*f;
}
#define maxn 1000050
int n,m;
struct node {
int x,y;
}a[maxn],b[maxn];
bool cmp(node a,node b) {
return a.x==b.x?a.y>b.y:a.x>b.x;
}
int res=0;
signed main() {
in2(n,m);
For(i,1,n) {
int x,y;
in2(x,y);
a[i].x=x,a[i].y=x-y;
res+=a[i].x;
}
For(i,1,m) {
in2(b[i].x,b[i].y);
}
int i=1;
sort(a+1,a+n+1,cmp);
sort(b+1,b+m+1,cmp);
priority_queue<int,vector<int>,greater<int> > q;
For(j,1,m){
while(i<=n&&a[i].x>=b[j].x) q.push(a[i].y),i++;
if(q.size()&&q.top()<b[j].y) {
q.pop();
q.push(b[j].y);
}
}
while(i<=n) q.push(a[i].y),i++;
while(q.size()) res-=q.top(),q.pop();
cout<<res;
}