1 条题解
-
0
#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
- 上传者