当贪心+二分 WA on #6
查看原帖
当贪心+二分 WA on #6
540363
AKPC楼主2023/1/12 12:24
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct node{
	int w,v;
}t[1000010];
int n,m,a[1000010],f[1000010],ans=0;
bool tmp[1000010]={0};
bool comp(node o,node p) {return o.v>p.v;}
signed main(){
// 	freopen("lopov.in","r",stdin);
// 	freopen("lopov.out","w",stdout);
	n=read(),m=read();
	for (int i=1;i<=n;i++) t[i].w=read(),t[i].v=read();
	for (int i=1;i<=m;i++) a[i]=read();
	sort(a+1,a+m+1);
	for (int i=1;i<a[m];i++){
		int l=1,r=m,mid=(l+r)/2;
		while (l<r){
			if (a[mid]==i) break;
			else if (a[mid]>i) r=mid;
			else l=mid+1;
			mid=(l+r)/2;
		}
		f[i]=mid;
//		cout<<f[i]<<' ';
	}
	sort(t+1,t+n+1,comp);
	for (int i=1;i<=n;i++){
		if (t[i].w>a[m]) continue;
		while (tmp[f[t[i].w]]&&f[t[i].w]<=m) f[t[i].w]++;
		if (f[t[i].w]>m) continue;
		tmp[f[t[i].w]]=1,ans+=t[i].v;
	}
	cout<<ans;
	return 0;
}

吸氧

2023/1/12 12:24
加载中...