深信服笔试题
程序员文章站
2024-03-15 17:49:42
...
对应LeetCode 453题(刷题的重要性)
题目描述:
给定一个长度为 n 的非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
示例:
输入:
[1,2,3]
输出:
3
解释:
只需要3次移动(注意每次移动会增加两个元素的值):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
比如输入[1,1,8,10,10,6]升序排序得[1,1,6,8,10,10]
index = 1 从[1,1,6,8,10,10]到达[1,1,6,8,10,10],(在此之前花费了0次,nums[1]和nums[0]的间距为0,之前的间距为0,现在间距为0)花费0次(一共花费0次)
index = 2 从[1,1,6,8,10,10]到达[6,6,6,13,15,15],(在此之前花费了0次,nums[2]和nums[1]的间距为5,之前的间距为0,现在间距为5)花费5次(一共花费5次)
index = 3 从[6,6,6,13,15,15]达到[13,13,13,13,22,22],(在此之前花费了5次,
nums[3]和nums[2]的间距为2,之前的间距为 5,现在间距为7)花费7次(一共花费12次)
index = 4 从[13,13,13,13,22,22]到达[22,22,22,22,22,33],(在此之前花费了12次,nums[4]和nums[3]的间距为2,之前的间距为7,现在间距为9)花费9次(一共花费21次)
index = 5 从[22,22,22,22,22,33]到达[33,33,33,33,33,33],(在此之前花费了21次,nums[5]和nums[4]的间距为2,之前的间距为9,现在间距为11)花费11次(一共花费32次)
class Solution {
public:
int minMoves(vector<int>& nums) {
unsigned long long result = 0, numsSize = nums.size(), distance = 0;
sort(nums.begin(), nums.end());//从小到大排序
for (int index = 1; index < numsSize; ++index){
//当前间距 == 上一次间距 + 此时间距
distance = distance + nums[index] - nums[index - 1];
result += distance;
}
return result;
}
};
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> trees(n, 0);
for (int i = 0; i < n; ++i) {
cin >> trees[i];
}
sort(trees.begin(), trees.end());
vector<long long> dp(n, 0); //可以滚动数组优化空间,不过我觉得dp数组写起来顺手
long long sum = 0;
long int distance=0;
for(long int i=1;i<n;i++){
distance+=(trees[i]-trees[i-1]);
sum+=distance;
}
cout << sum << endl;
}
return 0;
}
上一篇: JAVA的类与对象
下一篇: python 类和对象