站外题50pts求助,赏两关
  • 板块灌水区
  • 楼主WangCurry
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/25 13:35
  • 上次更新2024/10/25 15:58:18
查看原帖
站外题50pts求助,赏两关
764518
WangCurry楼主2024/10/25 13:35

有n个物品,物品有两个值ai,bia_i,b_i ,如果有物品x和y, ax<aya_x<a_ybx<ayb_x<a_y ,则物品y会被丢弃

问有多少个物品会被丢弃

1n1e6,1ai,bi1e91 \leq n \leq 1e6,1\leq a_i,b_i\leq1e9

#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 13:35
加载中...