题解 P1650 【田忌赛马】

顾z

2018-09-24 19:16:58

Solution

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 题目描述--->[p1650 田忌赛马](https://www.luogu.org/problemnew/show/P1650) ### 先%dalao sto [GMPotlc ](https://www.luogu.org/space/show?uid=87956) orz ~~他教给的我,征求意见后终于来水题解~~. ## 分析 我们需要知道的是如何决策,才能让田忌胜利次数最多. ~~n<=2000?~~ 我们可以自认为是田忌来**模拟这个过程**~~(穿越?~~) 值得考虑的是,我们每次调换每匹马的位置会白白增加复杂度。 因此我们找规律(说不上是真正意义上的找规律 qwq.) **这里只给出一个例子,不太理解的话还请大家手推一下** qwq. 排序之后,我们得到的序列为这样.(这里按数组下标来解释) 1即代表能力值最低,5代表能力值最高. ![](https://i.loli.net/2018/09/24/5ba8c7479cf24.png) 因为排序之后排名都一样. 这时我们考虑将后两匹马提前. 对应的就是这个样子啦 qwq ![](https://i.loli.net/2018/09/24/5ba8c7528106e.png) 我们不必去真正的模拟这个交换的过程. ### 为啥? 上图中我们的 4 5 1 2 3 实际上对应原序列的是 1 2 3 4 5 如何找到规律? 我们发现从1到len(此时len为2 位置对应的是我们后面的n到n-len. 此时我们得到的**对应关系就是 n-len+i 与 i 对应.** 而我们从len+1到n 位置对应的是我们前面的1-len. 此时我们又得到一组**对应关系就是 i-len与 i 对应.** (这两组关系如果得到一组的话我们就可以得到另一组~~应该是~~ 如果不太理解的话最好还是自己多手出几组尝试一下. -------------------代码------------------ ```cpp #include<bits/stdc++.h> #define R register using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,tianji[2508],qiwang[2508],ans; int main() { in(n); for(R int i=1;i<=n;i++)in(tianji[i]); for(R int i=1;i<=n;i++)in(qiwang[i]); sort(tianji+1,tianji+n+1); sort(qiwang+1,qiwang+n+1); for(R int len=1;len<=n;len++) { R int cnt=0; for(R int i=1;i<=len;i++) { if(tianji[n-len+i]>qiwang[i]) cnt++; if(tianji[n-len+i]<qiwang[i]) cnt--; } for(R int i=len+1;i<=n;i++) { if(tianji[i-len]>qiwang[i]) cnt++; if(tianji[i-len]<qiwang[i]) cnt--; } ans=max(ans,cnt); } printf("%d",ans*200); } ``` 有不理解的地方来~~gay~~私信我就好了 qwq 再度sto [GMPotlc ](https://www.luogu.org/space/show?uid=87956) orz