题解 P2123 【皇后游戏】

恕我直言，完成这道题，大体可以分为两个步骤： 1，找到**正确的贪心策略**，然后根据这个策略写出sort排序的bool函数，注意一定要定义一个**结构体**，再用**sort**排序一遍，这样我们就可以得到一个我们想要的让max最小的序列。 2，排序后贪心就完成了，接下来只需要按照题目所述的要求进行**模拟**。模拟完了，答案就出来了。 先来说说第一步，根据： c[1]=a[1]+b[1]; c[i]=max(c[i-1],(a[1]+a[2]+...+a[i]))+b[i]。(1<i<=n) 可以看出，前后两个大臣，后面的肯定比前面的得到的钱多，所以题中所谓的“**拿钱最多的大臣”不过是指站在最后的大臣**。这是很简单就能看出来也是很重要的一步。然后，我们开始思考贪心的策略。 我们在做比较简单的贪心题的时候，每一步都是在都贪心，即找到最优方案。每一步贪，最后得到的便是最优的，这道题也一样：根据刚刚我们得到的结论，如果我们在**每一次小小的排序中取最优解**的话，那么排完序得到最后一个大臣的也便是最优解了。所以，我们先从两个大臣排序的情况入手： c[2]=a[1]+b[2]+max(a[2],b[1])，我们再进行一下恒等变换 c[2]=(a[1]+a[2]+b[1]+b[2])-min(a[2],b[1]),排序一共有两种情况，这是第一种，1在2前面。 c[2]=(a[1]+a[2]+b[1]+b[2])-min(a[1],b[2]),这是第二种情况，2在1前面。 比较两种情况，发现区别就在min里面：如果a[1],a[2],b[1],b[2]四个数的最小值在a[1]或b[2]中，那么第一种情况的c[2]无疑比第二种情况的c[2]要小，排序要将1排在2前面。反之，若在a[2]或b[1]中，那么把2排到1前面就是更好的选择了。看一下这一部分的代码： ```cpp struct dachen { int l,r; }zz[20005]; bool master_cmp(dachen a, dachen b) { if (a.l<=a.r&&a.l<=b.l||b.l<=a.l&&b.l<=b.r) {//若a.l或b.l中有可以碾压对方两组的 if (a.l!=b.l) return a.l<b.l; return a.r>b.r;//若a.l与b.l相等就换一边 } if (a.r!=b.r)//下面的意思同上一个if里的一样 return a.r>b.r; return a.l<b.l; } ``` 刚刚，我们通过贪心完成了此题最难想的一步，接下来，只需要通过模拟推出答案，这便是第二步。这一步的模拟思维难度较刚刚说的贪心低多了，代码也很容易实现。我们只需要一次从1到n的循环，每一出来都求一下那个大臣的钱数，最后出来的最后一个大臣的钱数，就是答案了。 直接上代码： ``` #include <cstdio> #include <algorithm> using namespace std; struct dachen { int l,r; }zz[20005]; bool master_cmp(dachen a, dachen b) { if (a.l<=a.r&&a.l<=b.l||b.l<=a.l&&b.l<=b.r) { if (a.l!=b.l) return a.l<b.l; return a.r>b.r; } if (a.r!=b.r) return a.r>b.r; return a.l<b.l; } int main() { int t,n,i; long long left,ans;//一定要注意long long! scanf("%d",&t); while (t--) { left=0; ans=0; scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d%d",&zz[i].l,&zz[i].r); sort(zz+1,zz+n+1,master_cmp); for (i=1;i<=n;i++) { left+=zz[i].l;//left表示到现在为止前面所有大臣的左手的和 if (ans<left)//按要求求每个人的钱数 ans=left+zz[i].r; else ans+=zz[i].r; } printf("%lld\n",ans); } return 0; } ``` 这道题现在看来，就是一个贪心的排序加模拟。难度集中在如何找到好的排序方法，根据贪心找到方法后，题目便变容易了。