[关闭]
@Junlier 2018-08-31T22:11:46.000000Z 字数 914 阅读 1907

luoguP2123 皇后游戏(贪心)

贪心

题目

洛谷题目chuanso

题解

有一篇好题解,我就懒得推式子了,毕竟打到电脑上还是很难的
牛逼题解传送门

code

  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 20050
  17. using namespace std;
  18. const int Inf=1e9;
  19. int T,n;
  20. struct DC{
  21. int le,ri;
  22. }ljl[N];
  23. il int read()
  24. {
  25. rg int s=0,m=0;rg char ch=getchar();
  26. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  27. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  28. return m?-s:s;
  29. }
  30. il int cmp(rg const DC &a,rg const DC &b)
  31. {
  32. return min(a.le,b.ri)<min(b.le,a.ri);
  33. }
  34. int main()
  35. {
  36. T=read();
  37. while(T--)
  38. {
  39. n=read();
  40. for(rg int i=1;i<=n;++i)
  41. ljl[i]=(DC){read(),read()};
  42. sort(ljl+1,ljl+n+1,cmp);
  43. rg lst ans=ljl[1].le+ljl[1].ri;
  44. rg lst tot=ljl[1].le;
  45. for(rg int i=2;i<=n;++i)
  46. {
  47. tot+=ljl[i].le;
  48. ans=max(ans,tot)+ljl[i].ri;
  49. }
  50. cout<<ans<<endl;
  51. }
  52. return 0;
  53. }

挺难想的,毕竟我推了近一个小时的式子

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注