列表

详情

NC220463. AquariumArrangement

描述

    You are an employee at the Benelux Aquarium for Piranhas and Catfish. The aquarium is hoping to expand its meagre selection of aquatic life, but lacks the funds to do so. You have been tasked to help promote the aquarium by taking photos of the two exhibits. Taking the first photo went swimmingly, because the catfish were very cooperative. For the piranhas, you have an arrangement of piranhas in mind that will look great on the photo. However, the only way to get the piranhas to move is by recklessly sticking your finger into the water to lure the piranhas. Your goal is to move the piranhas to the desired positions as quickly as possible without losing your finger in the process.

    The piranha exhibit can be divided into positions  from left to right. The exhibit contains  piranhas and every position is occupied by at most one piranha. You can stick your finger into any unoccupied position. This will lure the nearest piranha to the left of your finger and the nearest piranha to the right of your finger. These piranhas will swim towards your finger, moving forward one position per second. All other piranhas simply stay in place. A piranha will bite your finger if it reaches the same position, so you must pull your finger away before this happens. Pulling your finger away and sticking it into a different position does not take any time.

    For example, suppose there are piranhas at positions ,  and . If you stick your finger into the water at position , the piranhas will be at positions ,  and  after one second. You now have to pull your finger away to prevent the piranha at position  from biting your finger one second later. If you now stick your finger into the water at position , only the piranha at position  will move and will end up at position 2 after one second.

输入描述

The input consists of:
- One line containing two integers  (), the number of positions, and  (), the number of piranhas.
- One line containing  integers , the current positions of the piranhas.
- One line containing  integers , the desired positions of the piranhas.

输出描述

Output the minimum number of seconds needed to get all of the piranhas at the desired positions. If it is impossible to do so, output "impossible".

示例1

输入: 

9 3
3 7 9
3 5 9

输出: 

4

示例2

输入: 

8 3
1 5 8
2 4 7

输出: 

impossible

示例3

输入: 

20 6
1 4 7 10 13 20
2 5 8 11 14 17

输出: 

17

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 90ms, 内存消耗: 504K, 提交时间: 2021-04-04 09:58:25 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
using vll = vector<ll>;

int main() {
	ll n, k;
	cin >> n >> k;
	vll p(k), d(k), ss(k + 1);
	for (ll i = 0; i < k; i++)
		cin >> p[i];
	for (ll i = 0; i < k; i++)
		cin >> d[i];
	ll mini = 0, total = 0;
	for (ll i = 1; i <= k; i++) {
		ll s = ss[i - 1] + d[i - 1] - p[i - 1];
		mini = min(mini, s);
		total += s;
		ss[i] = s;
	}
	for (ll i = 0; i <= k; i++)
		ss[i] -= mini;
	total -= mini * (k + 1);
	ll t = 0, i = 0;
	while (t < total) {
		if (i == 0) {
			if (ss[i] == 0 || p[i] < 3) {
				i++;
			}
			else {
				ll s = min(ss[i], p[i] - 2);
				p[i] -= s;
				ss[i] -= s;
				t += s;
				i++;
			}
		}
		else if (i < k) {
			if (ss[i] == 0 || p[i] - p[i - 1] < 4) {
				i++;
			}
			else {
				ll s = min(ss[i], (p[i] - p[i - 1] - 2) / 2);
				p[i - 1] += s;
				p[i] -= s;
				ss[i] -= s;
				t += s;
				i--;
			}
		}
		else { // i == k
			if (ss[i] == 0 || n - p[i - 1] < 2) {
				cout << "impossible" << endl;
				return 0;
			}
			else {
				ll s = min(ss[i], n - p[i - 1] - 1);
				p[i - 1] += s;
				ss[i] -= s;
				t += s;
				i--;
			}
		}
	}
	cout << total << endl;
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 306ms, 内存消耗: 20320K, 提交时间: 2021-04-04 09:58:36 

R = lambda: list(map(int, input().split()))
[n, k], p, d = R(), R(), R()

ss = [0]
mini, total = 0, 0
for i in range(1, k + 1):
    s = ss[i - 1] + d[i - 1] - p[i - 1]
    mini = min(mini, s)
    total += s
    ss.append(s)
for i in range(k + 1):
    ss[i] -= mini
total -= mini * (k + 1)
t, i = 0, 0
impossible = False
while t < total:
    if i == 0:
        if ss[i] == 0 or p[i] < 3:
            i += 1
        else:
            s = min(ss[i], p[i] - 2)
            p[i] -= s
            ss[i] -= s
            t += s
            i += 1
    elif i < k:
        if ss[i] == 0 or p[i] - p[i - 1] < 4:
            i += 1
        else:
            s = min(ss[i], (p[i] - p[i - 1] - 2) >> 1)
            p[i - 1] += s
            p[i] -= s
            ss[i] -= s
            t += s
            i -= 1
    else:
        if ss[i] == 0 or n - p[i - 1] < 2:
            print("impossible")
            impossible = True
            break
        else:
            s = min(ss[i], n - p[i - 1] - 1)
            p[i - 1] += s
            ss[i] -= s
            t += s
            i -= 1
if not impossible:
    print(total)

上一题

© 2024 nowcoder.com