牛客 21545 贪心
链接:https://ac.nowcoder.com/acm/problem/21545
来源:牛客网
来源:牛客网
题目描述
牛牛有一群牛友,每只小牛都站在坐标轴上的某个位置,这群牛友很听牛牛的话,每当牛牛做个手势,每只小牛都会移动恰好X个单位的距离,要么向左,要么向右
现在告诉你每只小牛在移动前的位置,求移动之后最左边的牛与最右边的牛的最小距离
现在告诉你每只小牛在移动前的位置,求移动之后最左边的牛与最右边的牛的最小距离
输入描述:
第一行输入一个整数n (1 ≤ n ≤ 50),表示牛的数量 第二行输入n个数pi (-1e8 ≤ pi ≤ 1e8),表示每只牛的位置 第三行输入一个整数X (0 ≤ X ≤ 1e8)
输出描述:
输出一个整数
思路:
从小到大快排坐标,依次进行判断,第一次,第一个值向右,剩下的向左,第二次,第一二个值向右,其余向左依次以此类推。循环过程中不断更新最小距离。
#include<bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; int main() { int n; cin>>n; int a[101]; int b[101]; int num=inf; int i; for(i=0;i<n;i++) { cin>>a[i]; } sort(a,a+n); int k; cin>>k; for(i=0;i<n;i++) { for(int j=0;j<=i;j++) b[j]=a[j]+k; for(int j=i+1;j<n;j++) b[j]=a[j]-k; sort(b,b+n); num=min(num,b[n-1]-b[0]); } cout<<num<<endl; }