周报1.0

补题补题(///￣皿￣)○～

牛客1(4):ABDG

E:双生双宿之错:
小红定义一个数组是“双生数组”，当且仅当该数组大小为偶数，数组的元素种类恰好为 2种，且这两种元素的出现次数相同。例如{1,1,4,4,1,4} 是双生数组。
现在小红拿到了一个长度为偶数的数组，她可以进行若干次操作，每次操作将选择一个元素，使其加 1 或者减 1。小红希望你计算将该数组变成双生数组的最小操作次数。

找一个合理的平均值就行，注意左右两边的平均值相同就加1或减1

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100005];
map<int,int>mp;
void solve(){mp.clear();int n;cin>>n;if(n==2){int x,y;cin>>x>>y;if(x==y)cout<<1<<endl;else cout<<0<<endl;return ;}for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]=1;}sort(a+1,a+1+n);int lmid=(n+3)/4;//找左半边的平均值int rmid=(n+1)/2+(n+3)/4;//找右半变的平均值的下标int ans=0;for(int i=1;i<=n/2;i++){ans+=abs(a[lmid]-a[i]);}int h=0;for(int i=(n/2)+1;i<=n;i++){ans+=abs(a[rmid]-a[i]);}//cout<<a[lmid]<<" "<<a[rmid]<<endl;//   cout<<h<<" "<<a[lmid]<<" "<<a[rmid]<<" "<<a[rmid+1]<<endl;if(a[rmid]==a[lmid]){//如果左边平均值下标对应的值等于右边平均值下标对应的值//就说明他们会变成一样的数，那么需要将两外一边全部加1就行int x=0,y=0;ans+=n/2;int num=0;for(int i=1;i<=n;i++){if(a[rmid]+1<=a[i])num++;//原先比他大的数经过减法变成平均数现在需要比平均数大说明减多了，加回来就行}x=num*2;num=0;for(int i=1;i<=n;i++){if(a[rmid]-1>=a[i])num++;}y=num*2;ans-=max(x,y);}cout<<ans<<endl;return ;
}
signed main(){int t;cin>>t;while(t--){solve();}return 0;
}

H:井然有序之窗
小红希望你构造一个长度为 n 的排列，需要满足第 iii 个元素的范围在 [li,ri]范围内。你能帮帮她吗？长度为 n排列是由 1∼n这 n个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{2,3,1,5,4} 是一个长度为 5的排列，而{1,2,2} 和 {1,3,4}\{1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

从左端点开始依次放入，右端点越近的先输出

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int>>a[100005];
int res[100005];
signed main(){int n;cin>>n;priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;for(int i=1;i<=n;i++){int l,r;cin>>l>>r;a[l].push_back({r,i});}for(int i=1;i<=n;i++){while(!a[i].empty()){q.push({a[i].back()});a[i].pop_back();}if(q.empty()||(!q.empty()&&q.top().first<i)){cout<<"-1"<<endl;return 0;}else{res[q.top().second]=i;q.pop();}}for(int i=1;i<=n;i++){cout<<res[i]<<" ";}return 0;
}

M:数值膨胀之美

定义一个数组的极差为：数组的元素最大值减去最小值。小红拿到了一个数组，她准备进行恰好一次操作：选择一个非空区间，将其中所有元素都乘以 2.小红希望最小化数组的极差，你能帮帮她吗？

写这题思想好乱，写不清楚😵

#include<bits/stdc++.h>
using namespace std;
#define int long long
pair<int,int>a[202020];
int b[202020];
signed main(){int n,i;cin>>n;for(i=0;i<n;i++){cin>>a[i].first,a[i].second=i;b[i]=a[i].first;}a[n].first=2e9;sort(a,a+n);int l=a[0].second,r=a[0].second;//排序后的数组//假设 1 1 2 2 3 4 5int ma=max(a[0].first*2,a[n-1].first);//一开始的最大值有两种可能//第一种是最小值的两倍或者是最大值本身int res=ma-min(a[0].first*2,a[1].first);//最小值可能是最小值的两倍或则次小值for(i=1;i<n;i++){//将第i个数字最为最小值左右两边扩展看看最大值是谁while(a[i].second<l){l--;ma=max(ma,b[l]*2);}while(a[i].second>r){r++;ma=max(ma,b[r]*2);}res=min(res,ma-min(a[0].first*2,a[i+1].first));}cout<<res;
}