1 条题解

  • 0
    @ 2022-6-19 21:44:54
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int n;
    int ans;
    struct node{
    	double l,s,cmp;
    }k[100100];
    bool cmp(node x,node y){
    	return x.cmp<y.cmp;
    }
    double a[10001][10001];
    int cnt[10001];
    inline int read(){
    	int x=0,f=1;
    	char c=getchar();
    	while(c>'9'||c<'0'){
    		if(c=='-') f=-1;
    		c=getchar();
    	}
    	while(c>='0'&&c<='9'){
    		x=(x<<3)+(x<<1)+(c^48);
    		c=getchar();
    	}
    	return x*f;
    }
    int main(){
    	n=read();
    	int aa,bb,cc;
    	for(int i=1;i<=n;i++){
    		aa=read();
    		bb=read();
    		cc=read();
    		k[i].l=(bb+cc)*1.0/aa;
    		k[i].s=bb*1.0/(aa+cc);
    		k[i].cmp=aa+bb+cc;
    	}
    	sort(k+1,k+1+n,cmp);
    	a[1][1]=k[1].s;
    	a[1][2]=k[1].l;
    	cnt[1]=2;
    	for(int i=2;i<=n;i++){
    		int t=1;
    		while(a[i-1][t]<k[i].s&&t<=cnt[i-1]){
    			a[i][t]=a[i-1][t];
    			t++;
    		}
    		int l=t;
    		cnt[i]=t-1;
    		if(t%2==1){
    			a[i][++cnt[i]]=k[i].s;
    			if(a[i-1][t]==a[i][t]) l=t+1;
    		} 
    		while(a[i-1][t]<=k[i].l&&t<=cnt[i-1]){
    			t++;
    		}
    		int r=t;
    		if(t%2==1){
    			a[i][++cnt[i]]=k[i].l;
    			if(a[i-1][t-1]==a[i][cnt[i]]) r--;
    		} 
    		while(t<=cnt[i-1]){
    			a[i][++cnt[i]]=a[i-1][t]; 
    			t++;
    		}
    		if(r-l>=1) ans++;
    		else{
    			if(r%2==1) ans++;
    		}
    	}
    	cout<<ans+1;
    	return 0;
    }
    
    • 1

    信息

    ID
    303
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者