站外题50pts求助
  • 板块灌水区
  • 楼主WangCurry
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/25 10:16
  • 上次更新2024/10/25 13:05:07
查看原帖
站外题50pts求助
764518
WangCurry楼主2024/10/25 10:16

有n个物品,物品有两个值aia_i , bib_i,如果有物品x和y,axa_x>aya_ybxb_x>byb_y,则物品y会被丢弃

问有多少个物品会被丢弃

1n1e6,1ai,bi1e9 1 \leq n \leq 1e6,1 \leq a_i,b_i \leq 1e9

#include<bits/stdc++.h>
using namespace std;const int maxn=1e6+10;struct p{int w,c;}wc[maxn];int n,ans=0,maxx=0;
bool cmp(const p&a,const p&b){
	return (a.c==b.c)?(a.w>b.w):(a.c>b.c);
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>wc[i].w>>wc[i].c;
	sort(wc,wc+n,cmp);
	//for(int i=0;i<n;i++)cout<<wc[i].w<<" "<<wc[i].c<<"\n"; 
	for(int i=0;i<n;i++){
		if(maxx>wc[i].w)ans++;
		else maxx=max(maxx,wc[i].w);
	}
	cout<<ans;
	return 0;
}
2024/10/25 10:16
加载中...