C 数组平均
思路:题目令我们把k个数字换成其对应的平均值后,要求整个数组的最大值和最小值的差值最小。
考虑贪心,对于数字的选择,我们尽可能选择一些差值比较大的数字,换言之,则是对数组进行排序后,选择其最小值,次小值,最大值,次大值,以此类推,但由于这样进行选择,判断较为繁琐,所以正难则反,我们考虑最后保留下来的数字,通过上述我们会发现,最终保留下来的数字一定是一段连续的区间,且区间长度为 n − k n-k n−k,我们就可以将其看作一个滑动窗口,因此可以在 O ( n ) O(n) O(n)的时间复杂度内完成检验,具体使用前缀和进行维护即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
typedef pair<ll,ll> pll;
int mod=1e9+7;
const int maxv=4e6+5;
const double pi=acos(-1.0);
void solve()
{
int n,k;
cin>>n>>k;
vector<ll> a(n+5);
for(int i=1;i<=n;i++) cin>>a[i];
vector<ll> s(n+5);
sort(a.begin()+1,a.begin()+1+n);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
if(k==n){
cout<<0<<endl;
return ;
}
double ans=1e9;
int len=n-k;
for(int i=1;i+len-1<=n;i++){
double sum1=s[i-1]+s[n]-s[i+len-1];//滑动窗口外的总和
sum1=sum1*1.0/k;//选择k个数的平均值
double mx=max(1.0*a[i+len-1],sum1);
double mix=min(1.0*a[i],sum1);
ans=min(ans,mx-mix);
}
printf("%.6lf",ans);
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int t;
t=1;
// cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}
D 游游出游
思路:二分答案+最短路。
一道很板的题目,一开始把二分的时间复杂度想到nlogn了,导致没敢写。昏头了。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> ar;
int mod = 998244353;
const int maxv = 4e6 + 5;
const double pi=acos(-1.0);
int n,m,h;
vector<ar> e[N];
void add(int u,int v,int w,int d)
{
e[u].push_back({v,w,d});
e[v].push_back({u,w,d});
}
bool st[N];
int dis[N];
bool check(int x)//二分答案,正常跑djk即可
{
priority_queue<pll,vector<pll>,greater<pll> > q;
memset(dis,0x3f,sizeof(int)*(n+5));
dis[1]=0;
memset(st,0,sizeof(bool)*(n+5));
q.push({0,1});
//cout<<dis[n]<<endl;
while(!q.empty()){
auto [dt,u]=q.top();
q.pop();
if(st[u]) continue;
st[u]=1;
for(auto [v,w,d] :e[u]){
if(w<x) {//若当前的重量大于边的重量,则无法通过这条边,即无法对该边进行更新
continue;
}
if(dis[v]>dis[u]+d){
dis[v]=dis[u]+d;
q.push({dis[v],v});
}
}
}
//cout<<dis[n]<<endl;
if(dis[n]>h) return false;
return true;
}
void solve()
{
cin>>n>>m>>h;
for(int i=1;i<=m;i++){
int u,v,w,d;
cin>>u>>v>>w>>d;
add(u,v,w,d);
}
int l=0,r=1e9;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
// cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}