bzoj1034

发表于 | 分类于

应该是改编自USACO的田忌赛马？最好的情况好处理，直接套用田忌赛马思想，排序后从小的开始比较，可以比过就加分，

不行的话再看最大的能不能比过，能就加分，如果都不行那就用自己最弱的去怼掉对方最强的。对于最坏的情况很明显我们能看出就是对手最好的情况，所以我们按照刚才的策略对对手进行一波贪心，由于不管谁输谁赢或是平局，一局对两人带来的分数总和都是2，所以我们只要用n*2-对手的最优即可得到己方的最坏情况。

题目链接：bzoj1034

渣代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,ans;
int zj[100005],ds[100005];
int solve(int zj[],int ds[])
{
    int zi=1,di=1;
    int zn=n,dn=n;
    int m=n;
    int ans=0;
    while(m--)
    {
        if(zj[zi]>ds[di])
        {
            ans+=2;
            zi++;
            di++;
        }
        else if(zj[zn]>ds[dn])
        {
            ans+=2;
            zn--;
            dn--;
        }
        else 
        {
            ans+=(zj[zi]==ds[dn]);
            zi++;
            dn--;
        }
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&zj[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&ds[i]);
    sort(zj+1,zj+n+1);
    sort(ds+1,ds+n+1);
    printf("%d %d",solve(zj,ds),2*n-solve(ds,zj));
    return 0;
}