hdu 3015 树状数组+离散化

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <algorithm>
  4. using namespace std;
  5. struct data
  6. {
  7. __int64 order;
  8. __int64 orign;
  9. __int64 rank;
  10. };
  11. data heigh[100100], coor[100100];
  12. int cmp(const void *a, const void *b)
  13. {
  14. return ( (*(data *)a).order - (*(data *)b).order );
  15. }
  16. int cmp1(const void *a, const void *b)
  17. {
  18. return (*(data *)a).orign - (*(data *)b).orign;
  19. }
  20. /*__int64 cmp1(const void *a, const void *b)
  21. {
  22. }*/
  23. int main()
  24. {
  25. freopen("read.txt", "r", stdin);
  26. __int64 n;
  27. while(~scanf("%d", &n) )
  28. {
  29. for(int i=1; i<=n; i++)
  30. {
  31. scanf("%I64d", &coor[i].orign);
  32. scanf("%I64d", &heigh[i].orign);
  33. coor[i].order = i;
  34. heigh[i].order = i;
  35. }
  36. qsort(coor, n, sizeof(coor[0]), cmp1);
  37. qsort(heigh, n, sizeof(heigh[0]), cmp1);
  38. int sign1, sign2, flag1, flag2;
  39. sign1 = sign2 = 1;
  40. flag1 = coor[1].orign, flag2 = heigh[1].orign;
  41. for(int i=1; i<=n; i++)
  42. {
  43. if(coor[i].orign != flag1)
  44. {
  45. flag1 = coor[i].orign;
  46. coor[i].rank = i+1;
  47. sign1 = i+1;
  48. }
  49. else
  50. coor[i].rank = sign1;
  51. if(heigh[i].orign != flag2)
  52. {
  53. flag2 = heigh[i].orign;
  54. heigh[i].rank = i+1;
  55. sign2 = i+1;
  56. }
  57. else
  58. heigh[i].rank = sign2;
  59. }
  60. //qsort(coor, n, sizeof(coor[0]), cmp);
  61. //qsort(heigh, n, sizeof(heigh[0]), cmp);
  62. //前面是对的, 但是我不知道怎么离散化。
  63. }
  64. return 0;
  65. }





附件列表

     

    郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。