比赛 贪心题目练习 评测结果 WWWW
题目名称 旅行家的预算 最终得分 0
用户昵称 htl 运行时间 0.012 s
代码语言 C++ 内存使用 3.31 MiB
提交时间 2025-03-22 10:13:04
显示代码纯文本
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, m1, m2;
  4. struct node
  5. {
  6. int a;
  7. int b;
  8. };
  9. bool operator<(node a, node b)
  10. {
  11. return a.b < b.b;
  12. }
  13. bool operator>(node a, node b)
  14. {
  15. return a.b > b.b;
  16. }
  17. node na[100010], nb[100010];
  18. bool cmp(node a, node b)
  19. {
  20. return a.a < b.a;
  21. }
  22. int f(node* ab, int lon, int _n)
  23. {
  24. priority_queue<node, vector<node>, greater<node> > q;
  25. int ans = 0;
  26. int ll = _n;
  27. for (int i = 1; i <= lon; i++)
  28. {
  29. while (!q.empty() && q.top().b <= ab[i].a)
  30. {
  31. q.pop();
  32. ll++;
  33. }
  34. if (ll == 0)
  35. {
  36. continue;
  37. }
  38. q.push(ab[i]);
  39. ll--;
  40. ans++;
  41. }
  42. return ans;
  43. }
  44.  
  45. int main()
  46. {
  47. freopen("lyuxing.in","r",stdin);
  48. freopen("lyuxing.out","w",stdout);
  49. cin >> n >> m1 >> m2;
  50. for (int i = 1; i <= m1; i++)
  51. {
  52. cin >> na[i].a >> na[i].b;
  53. }
  54. for (int i = 1; i <= m2; i++)
  55. {
  56. cin >> nb[i].a >> nb[i].b;
  57. }
  58. sort(na + 1, na + m1 + 1, cmp);
  59. sort(nb + 1, nb + m2 + 1, cmp);
  60. int ans = 0, t = 0;
  61. int l = 0, r = n;
  62. int mid1, mid2;
  63. while (r - l > 2)
  64. {
  65. mid1 = l + (r - l) / 3;
  66. mid2 = r - (r - l) / 3;
  67. if (f(na, m1, mid1) + f(nb, m2, n - mid1) >
  68. f(na, m1, mid2) + f(nb, m2, n - mid2))
  69. {
  70. r = mid2;
  71. }
  72. else
  73. l = mid1;
  74. }
  75. ans = -1;
  76. for (int i = l; i <= r; ++i)
  77. {
  78. ans = max(f(na, m1, i) + f(nb, m2, n - i), ans);
  79. }
  80. cout << ans;
  81. return 0;
  82. }