比赛 20121009 评测结果 AAAAA
题目名称 木棍 最终得分 100
用户昵称 Makazeu 运行时间 0.015 s
代码语言 C++ 内存使用 2.00 MiB
提交时间 2012-10-09 19:46:00
显示代码纯文本
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. using namespace std;
  7. const int MAXN=5011;
  8. class Wood{public:int len,wei;}W[MAXN];
  9. int N,ans=0,now,nlen,nwei; bool flag[MAXN]={0};
  10.  
  11. bool cmp(const Wood&a,const Wood&b)
  12. {
  13. if(a.len!=b.len) return a.len<b.len;
  14. return a.wei<b.wei;
  15. }
  16.  
  17. inline void init()
  18. {
  19. scanf("%d\n",&N);
  20. for(int i=1;i<=N;i++)
  21. scanf("%d %d\n",&W[i].len,&W[i].wei);
  22. sort(W+1,W+1+N,cmp);
  23. }
  24.  
  25. inline void work()
  26. {
  27. for(int i=1;i<=N;i++)
  28. {
  29. if(flag[i]) continue; flag[i]=1;
  30. nlen=W[i].len,nwei=W[i].wei;
  31. for(int j=i+1;j<=N;j++)
  32. {
  33. if(flag[j]) continue;
  34. if(W[j].len<nlen || W[j].wei<nwei) continue;
  35. flag[j]=1; nlen=W[j].len,nwei=W[j].wei;
  36. } ans++;
  37. }
  38. printf("%d\n",ans);
  39. }
  40.  
  41. int main()
  42. {
  43. freopen("wooden.in","r",stdin);
  44. freopen("wooden.out","w",stdout);
  45. init();work();
  46. return 0;
  47. }