商城界面设计_千万别学网络工程_品牌关键词优化哪家便宜_网络优化主要做什么

T1

T2

这道题听同只因房大犇讲会了，采用的贪心
我们可以将所有的折扣都换成折扣券
然后就可以贪心了。具体贪心如下：

1. 讲价格按照从小到大排序，方便下面二分
2. 讲折扣力度，即$v$按照从小到大排序
3. 依次遍历每个折扣券，每次查询大于等于当前$w$ 的第一个数，这里采用$lowerbound$
4. 当某点被用过后就删点，用并查集维护
5. 最后注意每次查询的边界情况

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
const int N=1e6+10;
struct node{int a,b, c;
}e[N];
struct quan{int w,v;
}y[N*2];
int n,m;
#define PII pair<int,int>
int as[N];
priority_queue<PII,vector<PII>,less<PII> >q;
bool cmp(node a,node b){return a.a<b.a;
}
bool cmp2(quan a,quan b){return a.v>b.v;
}
int fa[N];
int get(int x){if(x==fa[x]) return x;else return fa[x]=get(fa[x]);
} 
int vis[N];
int ans=0;
signed main(){n=read(),m=read();int tot=m;for(int i=1;i<=n;i++){e[i].a=read(),e[i].b=read();as[i]=e[i].a;ans+=as[i];y[++tot].w=e[i].a,y[tot].v=e[i].a-e[i].b;}for(int i=1;i<=m;i++){y[i].w=read(),y[i].v=read();}for(int i=1;i<=n;i++){fa[i]=i;}sort(as+1,as+1+n);sort(e+1,e+1+n,cmp);sort(y+1,y+1+m+n,cmp2);for(int i=1;i<=m+n;i++){int k=lower_bound(as+1,as+1+n,y[i].w)-as;
//		cout<<y[i].w<<"__:"<<y[i].v<<"   "<<k<<"___"<<"  ";k=get(k);if(k>n||vis[k]||k==0) {
//			cout<<endl;continue;}vis[k]=1;
//		cout<<k<<endl;ans-=y[i].v;if(k==n) continue;fa[k]=get(k+1);}printf("%lld",ans);return 0;
}

考场上我写了贪心特殊性质部分分，如果想出第一个特殊性质的话，那就基本是正解了。但是我写的第二个，从小到大排序后依次遍历即可

#define PII pair<int,int>
priority_queue<PII,vector<PII>,greater<PII> >q;
void work2(){sort(e+1,e+1+n,cmp2);for(int i=1;i<=m;i++){q.push({y[i].w,y[i].v});}for(int i=1;i<=n;i++){if(e[i].a>q.top().first) {ans-=q.top().second;q.pop();}}printf("%lld",ans);
}