最短距离
题目描述：
在一条一维的直线上，存在着 n 台显示器和 n 个电源插座。老师给小蓝布置了个任务：负责将每台显示器通过电源线与一个插座相连接（每个插座最多只能给一台显示器供电）；同时，老师希望所消耗的电源线的长度尽可能的少，请你帮小蓝计算下电源线的最小消耗长度为多少？
为了便于计算，你只需要考虑直线距离即可。
解题思路：
贪心思路，序号最小的显示器连接序号最小的插座这样下来最终的距离一定是最小，用vector定义两个long long数组分别存储显示器序号和插座序号，使用vetcor能够直接调用sort进行排序，即sort(x.begin(),x.end()); 然后让对应位置的x[i] y[i] 相减并取绝对值即可，累加到distance上输出。
#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main(){ int n; cin >> n; //定义两个vector 后边可以用来直接排序 vector<long long> x(n); vector<long long> y(n); //分别输入显示器和插座的位置 for(int i = 0; i < n; i++){ cin >> x[i]; } for(int i = 0; i < n; i++){ cin >> y[i]; } //位置最小的显示器连接位置最小的插座 这样一定是最小 long long dis = 0; //对显示器和插座分别排序，确保最小对应最小 sort(x.begin(),x.end()); sort(y.begin(),y.end()); //注意要用绝对值 for(int i = 0; i < n; i++){ dis += abs(x[i] - y[i]); } cout << dis << endl; return 0; }画展布置
题目描述：
解题思路：
这个题目主要是用滑动窗口解决，即去遍历排好序的vector，看看长度为m的序列那个满足最小的要求，为什么只用最后一项减去第一项呢？ 这个涉及到一个数学公式，把这个式子展开之后满足裂项相消，能够简化计算步骤，消掉之后就只剩下最后一项的平方减去第一项的平方，减少计算量，然后遍历长度为m的窗口，取最小值输出就行了。 为什么要用滑动窗口呢？因为对于有些连续的数字他的平方差比看起来小的数字更小，比如1，10，11，12，1000；如果取前三项最小的，那平方之后相减就是120，但是如果选择10，11，12，那相减之后就是44，所以才要用滑动窗口遍历整个数组找到最小的值。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int n, m; cin >> n >> m; //定义vector方便排序 vector<long long> x(n); for(int i = 0; i < n; i++){ cin >> x[i]; } //从小到大排序 sort(x.begin(), x.end()); //初始化l 最好的情况就是这个值 long long l = x[m - 1] * x[m - 1] - x[0] * x[0]; //滑动窗口 长度为m //遍历长度为m的序列 取cur和l的最小值 for(int i = 0; i <= n - m; i++){ long long cur = x[i + m - 1] * x[i + m - 1] - x[i] * x[i]; l = min(cur, l); } cout << l << endl; return 0; }
