题解 P1650 【赛马】

XZYQvQ · 2017-05-16 21:17:04 · 题解

很好奇这题为什么标签是动归

就这么把我骗了进来

明明贪心很简单

搞两个链表存两个人马的速度

输入完了以后排序

然后对链表1进行n次滚动(即把链表1的首部元素接到链表1末尾），每次移动以后判断当前答案。

最后取答案最大值。

ans的初始值一开始我设置为INT_MIN，这样在luogu上能ac，但在codevs上会wa两个点。

看了下数据，可能是标程的问题吧（不清楚），把ans的初始值设置为0就能过了（可能标程里ans初始值就是0）。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,ans;
list<int> l1,l2;
void update()
{
    int k=0;
    for(list<int>::iterator i1=l1.begin(),i2=l2.begin();i1!=l1.end();i1++,i2++)
        if(*i1>*i2)k++;else if(*i1<*i2)k--;
    ans=max(ans,k);
}
int main()
{
    scanf("%d",&n);
    for(int i=1,a;i<=n;i++)scanf("%d",&a),l1.push_back(a);
    for(int i=1,a;i<=n;i++)scanf("%d",&a),l2.push_back(a);
    l1.sort(),l2.sort();
    for(int i=1;i<=n;i++)l1.push_back(*l1.begin()),l1.pop_front(),update();
    printf("%d\n",ans*200);
    return 0;
}