Guest User

Untitled

a guest
Dec 26th, 2013
292
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <set>
  6. #include <ctime>
  7. #include <cstdlib>
  8. using namespace std;
  9.  
  10. int solve_e_maxx(vector< pair< int ,int> > a, int n)
  11. {
  12. sort(a.begin(), a.end());
  13. vector< int > res;
  14. set< pair<int , int > > se;
  15. for(int i = n-1; i >= 0; -- i)
  16. {
  17. int t = a[i].first-(i?a[i-1].first:0);
  18. se.insert( make_pair(a[i].second,i) );
  19. while(t && !se.empty())
  20. {
  21. set< pair<int,int> >::iterator it = se.begin();
  22. if(it->first <= t)
  23. {
  24. t-=it->first;
  25. res.push_back(it->second);
  26. }
  27. else
  28. {
  29. se.insert( make_pair(it->first-t, it->second) );
  30. t = 0;
  31. }
  32. se.erase(it);
  33. }
  34. }
  35. return res.size();
  36. }
  37.  
  38. int solve_algo( vector< pair<int, int> > a, int n)
  39. {
  40. sort(a.begin(), a.end());
  41. set< pair<int , int > > se;
  42. int T = 0;
  43. for(int i = 0; i < n; ++ i)
  44. {
  45. if(T+a[i].second <= a[i].first)
  46. {
  47. T+=a[i].second;
  48. se.insert( make_pair( -a[i].second ,i) );
  49. }
  50. else
  51. if(!se.empty())
  52. {
  53. set< pair<int, int> >::iterator it = se.begin();
  54. if(-(it->first) > (a[i].second))
  55. {
  56. T = T+(a[i].second)-(-(it->first));
  57. se.erase(it);
  58. se.insert( make_pair(-a[i].second, i));
  59. }
  60. }
  61. }
  62. return se.size();
  63. }
  64.  
  65. int main()
  66. {
  67. srand(time(NULL));
  68. freopen("input.txt", "r", stdin);
  69. freopen("output.txt", "w", stdout);
  70. int n;
  71. /* while(1)
  72. {
  73. n = rand()%100+1;*/
  74. cin>>n;
  75.  
  76. vector< pair<int, int > > a(n);
  77. /* for(int i = 0; i < n; ++ i)
  78. {
  79. a[i].first = rand()%10000+1;
  80. a[i].second = rand()%(10000)+1;
  81. }*/
  82.  
  83. for(int i = 0;i < n; ++ i)
  84. {
  85. cin>>(a[i].first)>>(a[i].second);//completion, duration
  86. }
  87.  
  88. int re1 = solve_e_maxx(a, n);
  89. int re2 = solve_algo(a, n);
  90. // cout<<re1<<" "<<re2<<endl;
  91.  
  92.  
  93. if(re1!=re2)
  94. {
  95. cerr<<"Wrong answer\n";
  96. cout<<n<<endl;
  97. for(int i = 0; i < n; ++ i)
  98. {
  99. cout<<a[i].first<<" "<<a[i].second<<endl;
  100. }
  101. // break;
  102. }
  103. //}
  104. return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment