POJ 2287

矫情吗；* 2023-08-17 16:37 18阅读 0赞

题意略。

思路：

田忌赛马。经典贪心。分别将田忌和齐王的马排序，设田忌最快和最慢的马分别为f1和s1，齐王的是f2和s2。

共有五种情况：1、f1 > f2，则有f1对阵f2，能赢齐王最快的马，当然是不二选择；

2、f1 < f2，则用s1和f2相比，因为肯定不能赢，用最慢的马去输代价最小；

3、f1=f2, s1 > s2，则s1与s2比赛，既然最慢的马能赢，没有必要浪费更快的马；

4、f1=f2, s1 < s2，则s1对抗f2，最慢的马肯定输，输给最快的马也算输得其所；

5、f1=f2，s1=s2，仍用s1对阵f2，这要证明。

显然，最优方案中，s1要么和f2比，要么和s2比。假设最优匹配是s1与s2配，x与f2配，交换s1和x，所得结果一定不会变差。因为：

若x < f2, 交换后有s1 < f2，x>=s2，可见结果没有变差；若x = f2，则交换后为s1=f2, x=s2或者s1 < f2, x > s2，二者结果都一样。

代码如下：

1 #include<iostream>
     2 #include<algorithm>
     3 #include<cstring>
     4 #include<cstdio>
     5 using namespace std;
     6 const int maxn = 1005;
     7 
     8 int king[maxn],general[maxn],n;
     9 int f0,l0,f1,l1;
    10 
    11 int main(){
    12     while(scanf("%d",&n) == 1 && n){
    13         for(int i = 0;i < n;++i) scanf("%d",&general[i]);
    14         for(int i = 0;i < n;++i) scanf("%d",&king[i]);
    15         
    16         sort(general,general + n);
    17         sort(king,king + n);
    18         reverse(general,general + n);
    19         reverse(king,king + n);
    20         
    21         int ans = 0;
    22         
    23         f0 = f1 = 0;
    24         l0 = l1 = n - 1;
    25         while(f0 <= l0){
    26             if(general[f0] > king[f1]){
    27                 ++ans;
    28                 ++f0;
    29                 ++f1;
    30             }
    31             else if(general[f0] < king[f1]){
    32                 --ans;
    33                 --l0;
    34                 ++f1;
    35             }
    36             else{
    37                 if(general[l0] > king[l1]){
    38                     ++ans;
    39                     --l0;
    40                     --l1;
    41                 }
    42                 else{
    43                     ans -= (general[l0] < king[f1] ? 1 : 0);
    44                     --l0;
    45                     ++f1;
    46                 }
    47             }
    48         }
    49         printf("%d\n",ans * 200);
    50     }
    51     return 0;
    52 }

转载于:https://www.cnblogs.com/tiberius/p/11509763.html

发表评论取消回复

表情：

评论列表（有 0 条评论，18人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ - 2287 Tian Ji -- The Horse Racing

题目来源 [2287 -- Tian Ji -- The Horse Racing (poj.org)][2287 -- Tian Ji -- The Horse Rac

桃扇骨/ 2023年10月12日 20:17/ 0 赞/ 109 阅读

相关 POJ 2287

题意略。思路：田忌赛马。经典贪心。分别将田忌和齐王的马排序，设田忌最快和最慢的马分别为f1和s1，齐王的是f2和s2。共有五种情况：1、f1 > f2，则有f1对阵

矫情吗；*/ 2023年08月17日 16:37/ 0 赞/ 19 阅读

相关 poj 1064 java_poj1064

Cable master Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 15127 Accept

r囧r小猫/ 2022年11月05日 03:30/ 0 赞/ 337 阅读

相关算法题目——田忌赛马(POJ-2287)

[POJ-2287][] [参考文章][Link 1] include<iostream> include<vector> i

拼搏现实的明天。/ 2022年09月10日 15:29/ 0 赞/ 297 阅读

相关【POJ】：POJ 3984

题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984] 题目解析：这题算是搜索里面的简单题了吧

Myth丶恋晨/ 2022年08月23日 04:50/ 0 赞/ 335 阅读

相关 POJ Tautology

Tautology <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

た入场券/ 2022年07月10日 04:16/ 0 赞/ 299 阅读

相关 poj1321+poj2251

poj1321代码实现（dfs）： include <iostream> include <string.h> using namespace std

心已赠人/ 2022年05月30日 04:08/ 0 赞/ 309 阅读

相关一天一算法-poj2287-田忌赛马

田忌赛马（贪心\+动规dp） Poj2287 Tian Ji -- The Horse Racing <table> <tbody> <tr> <t

忘是亡心i/ 2022年05月24日 20:44/ 0 赞/ 306 阅读

相关 poj1007

1．链接地址 [https://vjudge.net/problem/POJ-1007][https_vjudge.net_problem_POJ-1007] 2．问题描述

深藏阁楼爱情的钟/ 2021年11月23日 15:38/ 0 赞/ 350 阅读

相关 [bzoj2287]消失之物题解(背包dp)

2287: 【POJ Challenge】消失之物 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1138 So

矫情吗；*/ 2021年10月29日 08:52/ 0 赞/ 358 阅读