牛客网第三次模拟笔试----编程第三题

题目

大意，就是有一个数组

eg input[1,5,2,6]

要输出的结果就是一个相同大小的数组h h[i]代表的含义就是，将输入数组中的每一位都变成input[i]所需与的操作数，操作只允许在别的位上加1或者减一

思路

思路就是前缀和，如过数组长度比较小，那么就可以用map来进行题解

什么是前缀和，前缀和有什么用

sum[i]代表的是[0---i-1]的这个一个区间的和

那么好处和作用就很明显，就是能够快速的计算某一个区间的和

那么以 [1,5,2,6]为例，要把所有的数都变成1,那么其实就只需要知道整个数组的和减取数组个数*1的绝对值。

也就是abs(1+5+2+6-(1*4))=10

那么同样的要把所有的数字变成5,按照上面的思路有

以5结尾的和减去前面数的个数*5的绝对值 + 5开头到结尾的和减去后面的个数*5的绝对值

也就是abs(1+5-(2*5))+abs(5+2+6-(3*5)) = 4+2=6 || 但是实际上是8

为什么呢，其实就是，[+4,0,+3,-1],明显就是后面的正负抵消了，所以算出来是6，这时候怎么解决，就要把正的全部放在后面，负的全部就要放在前面，就需要排序。同时需要记住下标，这样才可以记住在哪里插入

程序

#include <algorithm>
#include <iostream>
#include <vector>using namespace std;vector<int> GetRes(vector<int>& data) {vector<pair<int, int>> sort_data;for (int i = 0; i < data.size(); i++) {sort_data.push_back({data[i], i});}// 自定义排序函数auto cmp = [&](pair<int, int>& a, pair<int, int>& b) -> bool {if (a.first < b.first) {return true;} else {return false;}};// 排序sort(sort_data.begin(), sort_data.end(), cmp);//   for (auto value : sort_data) {
//     cout << value.first << " " << value.second << " | ";
//   }
//   cout << endl;// 进行前缀和计算vector<int> res(data.size());vector<int> sum(data.size() + 1);data[0] = 0;for (int i = 0; i < sort_data.size(); i++) {sum[i + 1] = sum[i] + sort_data[i].first;}// 开始进行计算，注意前缀和的意义就是[0~i-1]个数字的和// 开始进行计算for (int i = 0; i < sort_data.size(); i++) {int result = 0;// 计算前半部分int front = abs(sum[i + 1] - sort_data[i].first * (i + 1));// 计算后半部分int back =abs(sum[data.size()] - sum[i] - sort_data[i].first * (data.size() - i));result = front + back;res[sort_data[i].second] = result;}return res;
}int main() {vector<int> data = {2, 3, 3, 5, 1};auto res = GetRes(data);for (auto value : res) {cout << value << " ";}cout << endl;
}