HDU1052

题目链接

传送门

题目大意

题意是田忌赛马的变形,胜一场得200,输一场失200,平局不得分。第一行n代表n匹马,然后一行输入田忌马的速度, 接下来输入国王马的速度,最后求田忌的金币数。

解题思路

首先对t和k的数组进行从小到大排序。首先比较最小的,如果t最小的马能赢k最小的马的话,那就win++,如果t最 小的马不能赢的话,就让它跟k最大的马比,把k最大的马刷掉,同时lose++。平局的时候要多加考虑,因为t输一场、赢一 场和平局最后的收益一样大,如果t最大的马比k最大的马小的话,那么此时用t最小的马去刷点k最大的马,即故意输一局, 这无疑会给t最大的马减轻不少压力,尽管此时输了一局,但在之后t的马中一定能有把k当前最小马刷掉的马,所以说输一局、 赢一局和平局收益相同。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <cassert>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
#define REP0(i, n) for (int i=0;i<int(n);++i)  
#define REP1(i, n) for (int i=1;i<=int(n);++i)  
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)  
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)  
using namespace std;  
#define REP(i, n) for (int i=0;i<int(n);++i)  
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)  
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)  
#define REP_1(i, n) for (int i=1;i<=int(n);++i)  
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)  
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)  
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)  
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)  
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)  
#define REP_N(i, n) for (i=0;i<int(n);++i)  
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)  
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)  
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)  
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)  
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)  
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)  
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)  
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)  
#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)  
#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)  
#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)  
#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)  
#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)  
#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)  
#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)  
#define REP_S(it, str) for (char*it=str;*it;++it) // 用于字符串的 .. .  
#define REP_G(it, u) for (int it=hd[u];it;it=suc[it]) // 用于图论的 .. .  
#define DO(n) for ( int ____n ## __line__ = n; ____n ## __line__ -- ; )  
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)  
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)  
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)  
#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)  
#define PB push_back  
#define MP(A, B) make_pair(A, B)  
#define PTT pair<T, T>  
#define fi first  
#define se second  
#define Display(A, n, m) {                      \  
    REP(i, n){                                  \  
        REP(j, m) cout << A[i][j] << " ";       \  
        cout << endl;                         \  
    }                                           \  
}  
#define Display_1(A, n, m) {                    \  
    REP_1(i, n){                                \  
        REP_1(j, m) cout << A[i][j] << " ";     \  
        cout << endl;                         \  
    }                                           \  
}  
typedef long long LL;  
typedef double DB;  
typedef unsigned UINT;  
typedef unsigned long long ULL;  
const int dx[] = {-1, 0, 1, 0};  
const int dy[] = {0, 1, 0, -1};  
const int MOD = 1000000007;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 1LL << 60;  
const DB EPS = 1e-9;  
const DB OO = 1e15;  
const DB PI = acos(-1.0); //M_PI;  

#define N 100010  

int a[N] , b[N] , vis[N];  

int main()  
{  
    #ifdef ZH  
    freopen("in.txt","r",stdin);  
    #endif  
    int n;  
    while(~scanf("%d",&n))  
    {  
        if(n == 0)  
            break;  
        REP(i , n)  
        {  
            scanf("%d",&a[i]);  
            vis[i] = 0;  
        }  
        REP(i , n)  
            scanf("%d",&b[i]);  
        sort(a , a + n);  
        sort(b , b + n);  
        int win = 0 , lose = 0;  
        int tl = 0 , tf = n - 1;  
        int kl = 0 , kf = n - 1;  
        while(tl <= tf)  
        {  
            if(a[tl] > b[kl])  
            {  
                win ++;  
                tl ++;  
                kl ++;  
            }  
            else if(a[tl] < b[kl])  
            {  
                lose ++;  
                tl ++;  
                kf --;  
            }  
            else  
            {  
                if(a[tf] > b[kf])  
                {  
                    win ++;  
                    tf --;  
                    kf --;  
                }  
                else  
                {  
                    if(a[tl] < b[kf])  
                    lose ++;  
                    tl ++;  
                    kf --;  
                }  
            }  

        }  
        printf("%d\n",200 * (win - lose));  
    }  
}  

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图