题目链接
时间复杂度
利用n个数放在n+1个桶中,必然有一个空桶,这也就否定了最大差值在桶内部。
然后记录每个桶中的最大值和最小值,最大差值在两个临近桶之间。
推荐看左神视频初级班第三讲100分钟左右
考查内容
桶排序
#include<bits/stdc++.h> using namespace std; const int INF = 0x3fffffff; typedef long long LL; LL m,n; vector<LL> arr; LL bucket(LL x,LL Max, LL Min){ return (x - Min)*n/(Max - Min); } int main(){ while(cin>>m){ LL Max = -INF, Min = INF; LL x; char c; while(cin>>x){ arr.push_back(x); if(x > Max) Max = x; if(x < Min) Min = x; c = getchar(); if(c =='\n') break; } n = arr.size(); if(Max == Min || n < 2){ cout<<0<<endl; continue; } //n+1个桶中放n个数 vector<bool> hasNum(n+1); //标记桶的状态 vector<LL> maxs(n+1),mins(n+1); //记录桶中的最大值和最小值 LL bid; for(LL i = 0; i < n; i++){ bid = bucket(arr[i], Max, Min); maxs[bid] = hasNum[bid]? max(maxs[bid], arr[i]) : arr[i]; //保存最大值 mins[bid] = hasNum[bid]? min(mins[bid], arr[i]) : arr[i];//保存最小值 hasNum[bid] = true; } LL res = 0; LL lastMax = maxs[0]; for(LL i = 1; i <= n; i++){ //n+1个桶 if(hasNum[i]){ res = max(res, mins[i] - lastMax); //全部桶里面找 lastMax = maxs[i]; } } cout<<res<<endl; } return 0; }