gym102392 I. Absolute Game

gym102392 I. Absolute Game

题目链接

题意

Alice有一个长度为

n

n

n的序列

a

a

a,Bob有一个长度为

n

n

n的序列

b

b

b,Alice先手。

每次操作,玩家从自己的序列中扔掉一个元素,直到只剩一个元素时,不能进行操作,此时Alice剩下的元素为

x

x

x,Bob剩下的元素为

y

y

y

定义

r

e

s

=

x

y

res=|x-y|

res=xy,Alice想要使得

r

e

s

res

res尽可能的大,Bob想要使得

r

e

s

res

res尽可能的小。

思路

个人感觉不太好想的一道思维题,但是很容易凭感觉猜出答案。

若游戏结束后,

x

=

a

[

i

]

x=a[i]

x=a[i]​,则当

y

=

b

[

j

]

y=b[j]

y=b[j]​时

r

e

s

res

res​最小,将

i

i

i​和

j

j

j​连接起来,如下图:

在这里插入图片描述

若Alice第一步操作将

a

1

a_1

a1丢掉,则Bob将

b

1

b_1

b1丢掉,因为

b

1

b_1

b1只会和

a

1

a_1

a1产生最小的

r

e

s

res

res,而对其他的

a

i

a_i

ai不优,

a

1

a_1

a1丢掉后

b

1

b_1

b1就没用了,可以直接丢掉。

若Alice第一步操作将

a

2

a_2

a2丢掉,则Bob将

b

4

b_4

b4丢掉,因为

b

4

b_4

b4不可能和任何一个

a

i

a_i

ai产生最小的

r

e

s

res

res,但是

b

2

b_2

b2会和

a

4

a_4

a4产生最优解,所以

b

2

b_2

b2不能丢。

因此,无论Alice最后剩余哪个

a

i

a_i

ai​​,Bob都能剩下一个产生最小

r

e

s

res

res​​的

b

j

b_j

bj​​,则

r

e

s

res

res就是对所有

a

i

a_i

ai​​​的Min取一个Max。

AC的代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int n, a[N], b[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    int res = 0;
    for (int i = 1; i <= n; i++) {
        int tmp = 1e9 + 10;
        for (int j = 1; j <= n; j++) tmp = min(tmp, abs(a[i] - b[j]));
        res = max(res, tmp);
    }
    cout << res;
    return 0;
}

THE END
分享
二维码
< <上一篇
下一篇>>