[关闭]
@Junlier 2018-08-31T22:12:35.000000Z 字数 1162 阅读 1966

[JSOI2007]建筑抢修(贪心+后悔)

贪心——后悔操作
洛谷题目传送门

吐槽

这是一道经典的贪心后悔的题目
做过贪心加后悔的题目的应该一眼可以看出来

解题思路

  • 首先按倒塌时间T2排序,再从1枚举到n,能修就修,发现不能修就从前面找一个修的最慢的来后悔,当然,前提是这个最慢的要比现在要修的慢,不难证明这样肯定更优(节省了时间修后面的)。嗯,做完了,没了,代码实现基本没难度
  • 还有,用堆来维护前面修过的最大值。
    一般这类题都是堆吧......(具体情况具体讨论)

code(没注释QwQ)

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define N 150050
  17. using namespace std;
  18. const int Inf=1e9;
  19. int n,ans;
  20. struct HOUSE{
  21. int fixt,badt;
  22. bool operator<(rg HOUSE a)
  23. {
  24. return badt<a.badt;
  25. }
  26. }ljl[N];
  27. priority_queue<int>Q;
  28. il int read()
  29. {
  30. rg int s=0,m=0;rg char ch=getchar();
  31. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  32. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  33. return m?-s:s;
  34. }
  35. int main()
  36. {
  37. n=read();
  38. for(rg int i=1;i<=n;++i)
  39. ljl[i]=(HOUSE){read(),read()};
  40. rg int now=0;
  41. sort(ljl+1,ljl+n+1);
  42. for(rg int i=1;i<=n;++i)
  43. {
  44. if(now+ljl[i].fixt>ljl[i].badt)
  45. {
  46. if(!Q.empty())
  47. if(ljl[i].fixt<Q.top())
  48. {
  49. now-=Q.top()-ljl[i].fixt;
  50. Q.pop();
  51. Q.push(ljl[i].fixt);
  52. }
  53. }
  54. else
  55. {
  56. now+=ljl[i].fixt;
  57. Q.push(ljl[i].fixt);
  58. }
  59. }
  60. while(!Q.empty())ans++,Q.pop();
  61. printf("%d\n",ans);
  62. return 0;
  63. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注