首页 > 代码库 > hdu 2572 优先队列

hdu 2572 优先队列

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #include <queue>
  5. #define max_one 100
  6. #define max_two 50
  7. #define max_three 50
  8. using namespace std;
  9. struct node //structure must sign first
  10. {
  11. string str;
  12. int size;
  13. };
  14. struct cmp //return the most minimum string
  15. //pay attention :
  16. //must complete size first then complete string
  17. {
  18. bool operator() (const node &a, const node &b)
  19. {
  20. if(a.size >b.size)
  21. return true;
  22. else if(a.size ==b.size)
  23. return a.str>b.str;
  24. else return false;
  25. }
  26. };
  27. priority_queue <node, vector<node>, cmp> que;
  28. void score_string(char *p, char *q, int two, int three) //score string into queue
  29. {
  30. string temp="";
  31. if(p>q)
  32. {
  33. int length=three > p-q+two ? three : p-q+two;
  34. for(int i=0; i<length ;i++)
  35. temp+=*(q+i);
  36. node a;
  37. a.str=temp;
  38. a.size=length;
  39. que.push(a);
  40. }
  41. else if(p<q)
  42. {
  43. int length=two > q-p+three ? two : q-p+three;
  44. for(int i=0; i<length ;i++)
  45. temp+=*(p+i);
  46. node a;
  47. a.str=temp;
  48. a.size=length;
  49. que.push(a);
  50. }
  51. else if(p=q) //pay attention : p=q such as this string
  52. //one :asdfgh two :asdfgh three:a;
  53. {
  54. int length=two >three ? two :three;
  55. for(int i=0; i<length ;i++)
  56. temp+=*(p+i);
  57. node a;
  58. a.str=temp;
  59. a.size=length;
  60. que.push(a);
  61. }
  62. }
  63. int main()
  64. {
  65. int T;
  66. cin>>T;
  67. while(T--)
  68. {
  69. while(!que.empty() ) //each text must clean the queue
  70. {
  71. que.pop();
  72. }
  73. char one[max_one],two[max_two],three[max_three];
  74. cin>>one>>two>>three;
  75. int two_length=strlen(two); //score size of two three string
  76. int three_length=strlen(three);
  77. char *p=strstr(one,two);
  78. char *q=strstr(one,three);
  79. if(p==NULL ||q==NULL)
  80. cout<<"No"<<endl;
  81. else
  82. {
  83. char *two_point[max_two]; //set pointer array score the possible way of string
  84. char *three_point[max_three];
  85. two_point[0]=p;three_point[0]=q;
  86. int size_two=1;
  87. char *temp_two=p,*temp_three=q;
  88. while( (temp_two=strstr(temp_two+1,two))!=NULL) //get different substring way
  89. two_point[size_two++]=temp_two;
  90. int size_three=1;
  91. while( (temp_three=strstr(temp_three+1,three))!=NULL)
  92. three_point[size_three++]=temp_three;
  93. for(int i=0; i<size_two; i++) //score
  94. {
  95. for(int j=0; j<size_three; j++)
  96. score_string(two_point[i], three_point[j], two_length, three_length);
  97. }
  98. cout<<que.top().str<<endl;
  99. }
  100. //cout<<que.top().str<<endl;
  101. }
  102. return 0;
  103. }



来自为知笔记(Wiz)


附件列表

     

    hdu 2572 优先队列