牛客周赛 Round 17 C,D

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;
}