写在前面

本次给大家带来10月12日的小米笔试题的2道题，本套题目难度并不是很大，第一题更偏重于思维技巧，关键在于认识到每次反转两个数并不会改变负数个数的奇偶性，这一特性是正确解题的核心。第二题主要考察数据结构的应用，由于数据范围较大，普通的线性操作效率不足，必须使用双向链表来高效地优化插入和删除操作，从而提高算法的整体性能。

第1题-均衡

题目内容

小塔在研究一个有趣的数组翻转操作问题，其中为了考虑均衡，他会同时翻转相邻两个数。他有一个长度为的数组，并可以进行任意次操作:选择相邻的两个数，翻转这两个数的符号，即将和的符号都翻转。符号翻转的意思是正数变负数，负数变正数，在程序中即让，也即数学中的取相反数;当然翻转后还是。小明的任务是找到经过任意次数(可以为次)这些操作后，能够获得的最大数组和。当然，只要小明觉得有必要，同一个数也可以被反复选择。

输入描述

第一行包含一个整数，表示数组的长度。

第二行包含个整数，。

，。

输出描述

输出一个整数，表示经过任意次操作后数组的最大和

样例1

输入

5
1 -2 3 -4 5

输出

15

说明

在这个样例中，初始数组的和是''

通过选择相邻的和翻转符号成[]，再选择和翻转符号，使得数组变为'[]'，得到的和是'1+2+3+4+5=15$'。

思路

一种直观的想法是将数组中的所有数都反转为正数，这样数组的和就会最大。由于一个数可以被反转多次，我们可以从前往后依次将每个数反转为正数。然而，因为每次只能反转相邻的两个数，如果数组中负数的个数是奇数，那么必然有一个数无法变为正数。为了使数组和最大，我们可以选择让绝对值最小的数保持为负数，这样得到的数组和就是最大的。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n; 
    vector<long long> a(n);
    int count = 0;     
    long long sum = 0;       
    long long min_abs = LLONG_MAX; 
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] < 0) count++;
        long long abs_value = abs(a[i]);
        sum += abs_value;
        min_abs = abs_value < min_abs ? abs_value : min_abs;
    }
    if (count % 2 == 0)
        cout << sum << endl;
    else 
        cout << sum - 2 * min_abs << endl;
    return 0;
}

第2题-宝石项链

题目内容

小塔正在欣赏他的一串宝石项链。这个项链还没有封口，是一条链，初始时从左到右宝石分别编。然而经过一段时间端详，小塔觉得他应该把某颗宝石取下，然后放到某颗宝石的前面或者后面去，小塔在正式进行调整前，想请你帮他模拟一下他的若干次调整，希望你能告诉他经过他若干次调整后宝石项链的样子。

输入描述

第一行个空格隔开的整数n和q,表示宝石数量和操作次数。

第二行个空格隔开的整数,对第次操作,表示将编号为的宝石取下，放到编号为的宝石旁边，当,=时放到其前，否则放到其后。

,,。保证。

输出描述

输出一行个整数，表示调整后,从左到右宝石的编号。

样例1

输入

5 3
1 2 1 3 2 0 5 4 0

输出

3 2 1 5 4

说明

初始

第一次把取下，放到后，变成

第二次把取下，放到前，变成

第三次把取下，放到前，变成。

思路

这道题实际上需要维护一个动态链表，但由于数据范围较大，使用暴力解法（即使用 list 逐个查找每个数的位置进行插入和删除）无法通过测试。

为了解决这个问题，我们可以使用双向链表进行优化。需要记录每个节点，以便快速定位特定元素。由于双向链表的特性，在链表的前后插入节点都非常方便，关键在于正确实现双向链表的插入和删除操作。

代码

#include <iostream>
#include <unordered_map>
#include <cstdio>

struct Node {
    int val;
    Node* prev;
    Node* next;
    Node(int value) : val(value), prev(nullptr), next(nullptr) {}
};

void addBefore(Node* node, Node* nextNode) {
    Node* prevNode = nextNode->prev;
    node->next = nextNode;
    node->prev = prevNode;
    prevNode->next = node;
    nextNode->prev = node;
}

void addAfter(Node* node, Node* prevNode) {
    Node* nextNode = prevNode->next;
    node->next = nextNode;
    node->prev = prevNode;
    prevNode->next = node;
    nextNode->prev = node;
}

void removeNode(Node* node) {
    Node* prevNode = node->prev;
    Node* nextNode = node->next;
    prevNode->next = nextNode;
    nextNode->prev = prevNode;
}

int main() {
    int n, q;
    std::cin >> n >> q;

    std::unordered_map<int, Node*> nodeMap;
    Node* head = new Node(0);
    Node* tail = new Node(0);
    head->next = tail;
    tail->prev = head;

    for (int i = 1; i <= n; ++i) {
        Node* newNode = new Node(i);
        nodeMap[i] = newNode;
        addBefore(newNode, tail);
    }

    int x, y, op;
    for (int i = 0; i < q; ++i) {
        std::scanf("%d %d %d", &x, &y, &op);
        Node* X = nodeMap[x];
        Node* Y = nodeMap[y];

        removeNode(X);
        if (op == 0) {
            addBefore(X, Y);
        } else {
            addAfter(X, Y);
        }
    }

    Node* current = head->next;
    while (current != tail) {
        std::printf("%d%c", current->val, current->next == tail ? '\n' : ' ');
        current = current->next;
    }

    current = head;
    while (current != nullptr) {
        Node* temp = current;
        current = current->next;
        delete temp;
    }
    return 0;
}