最短距离题目描述在一条一维的直线上存在着 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 后边可以用来直接排序 vectorlong long x(n); vectorlong 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的窗口取最小值输出就行了。 为什么要用滑动窗口呢因为对于有些连续的数字他的平方差比看起来小的数字更小比如11011121000如果取前三项最小的那平方之后相减就是120但是如果选择101112那相减之后就是44所以才要用滑动窗口遍历整个数组找到最小的值。#include iostream #include vector #include algorithm using namespace std; int main(){ int n, m; cin n m; //定义vector方便排序 vectorlong 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; }
最短距离题目描述在一条一维的直线上存在着 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 后边可以用来直接排序 vectorlong long x(n); vectorlong 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的窗口取最小值输出就行了。 为什么要用滑动窗口呢因为对于有些连续的数字他的平方差比看起来小的数字更小比如11011121000如果取前三项最小的那平方之后相减就是120但是如果选择101112那相减之后就是44所以才要用滑动窗口遍历整个数组找到最小的值。#include iostream #include vector #include algorithm using namespace std; int main(){ int n, m; cin n m; //定义vector方便排序 vectorlong 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; }
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
