[原]Rabbits —— HDU-6227

王良 17/12/21 22:09:16

picture


题意:

有n只兔子在不同的位置,任意一只兔子可以跳到其余任两只兔子(必须保证它们中间有空位)中间,问最多可移动多少次?


思路:

可看作从任一侧的兔子向中间插空,因此可以将所有兔子中间的空位数相加,再减去两侧较小的数字(最左侧两只兔子间距离与最右侧两只兔子间距离的较小的值)。


AC代码:


#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int main() {
    int t, n, sum, addr[500];
    int front, rear;
    cin >> t;
    while(t--) {
        sum = 0;
        memset(addr, 0, sizeof(addr));

        cin >> n >> addr[0];
        for(int i = 1; i < n; i++) {
            cin >> addr[i];
            sum += addr[i] - addr[i-1] - 1;
        }

        front = addr[1] - addr[0] - 1;
        rear = addr[n-1] - addr[n-2] - 1;
        if(front <= rear) {
            sum -= front;
        } else {
            sum -= rear;
        }

        cout << sum << endl;
    }

    return 0;
}
作者:liushall 发表于 2017/12/21 22:09:16 原文链接 http://blog.csdn.net/liushall/article/details/78868294
阅读:26