【杭电1052】Tian Ji -- The Horse Racing

浅浅的花香味﹌ 2022-07-20 12:09 131阅读 0赞

![这里写图片描述][20160724113845406]  
![这里写图片描述][20160724113855719]  
![这里写图片描述][20160724113910407]  
![这里写图片描述][20160724113927079]  
应该算是贪心里的思维题，这种题没有固定的模板，选对贪心的标准就对了，本题标准就是每一步都要尽可能的使田忌获胜的可能性最大化。还有贪心就是做到局部最优解，从而得到全局最优。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int ti[1002],ki[1002],c[1002];
    int main() {
        int T=50;
        while(T--) {
            memset(c,-1,sizeof(c));
            int n,sum=0;
            scanf("%d",&n);
            if(n==0)
                break;
            for(int l=0; l<n; l++)
                scanf("%d",&ti[l]);
            for(int l=0; l<n; l++)
                scanf("%d",&ki[l]);
            sort(ki,ki+n);
            sort(ti,ti+n);
            int ti_max=n-1,ti_min=0;
            int ki_max=n-1,ki_min=0;
            while(ti_min<=ti_max) {
                if(ti[ti_min]>ki[ki_min]) {
                    sum++;
                    ti_min++,ki_min++;
                } else if(ti[ti_max]>ki[ki_max]) {
                    sum++;
                    ti_max--,ki_max--;
                } else {
                    if(ti[ti_min]<ki[ki_max])//重在理解这一步 
                        sum--;
                    ti_min++,ki_max--;
                }
            }
            printf("%d\n",sum*200);
        }
        return 0;
    }

[http://acm.hdu.edu.cn/showproblem.php?pid=1052][http_acm.hdu.edu.cn_showproblem.php_pid_1052]

[20160724113845406]: /images/20220719/7a42cc223d73481abbb74963b04688e1.png
[20160724113855719]: /images/20220719/68fbdd07e9fd412c9dab13231903ffe1.png
[20160724113910407]: /images/20220719/fb0ed922f43643b69847d00b773fa482.png
[20160724113927079]: /images/20220719/6ecbc0b3a6e14a5d8c4aa7954c6ff923.png
[http_acm.hdu.edu.cn_showproblem.php_pid_1052]: http://acm.hdu.edu.cn/showproblem.php?pid=1052