$D-排序加分类讨论$
$排序后分为左右两边,左边[1,\frac{n}{2}],右边[\frac{n}{2}+1,n]$
$如果n为偶数,删除一个后为奇数,直接取数字为中位数$
$如果删除的是左半边,取右边最小的b[\frac{n}{2}+1];如果删除的是右半边,取左边最大的b[\frac{n}{2}]$
$如果n为奇数,删除一个后为偶数$
$如果删除的是左半边:取右边最小的和次小的平均值\frac{b[\frac{n}{2}+1]+b[\frac{n}{2}+2]}{2}$
$如果删除的是右半边-最小的:取左边最大和右边次小的平均值\frac{b[\frac{n}{2}]+b[\frac{n}{2}+2]}{2}$
$如果删除的是右半边-非最小的:取左边最大和右边最小的平均值\frac{b[\frac{n}{2}]+b[\frac{n}{2}+1]}{2}$
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#define IOS cin.tie(nullptr)->ios::sync_with_stdio(false);
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
int b[N];
int n;
signed main(){
IOS
cin>>n;
double sum=0;
for(int i=1;i<=n;i++)
cin>>a[i];
if(n%2==0){
memcpy(b,a,sizeof a);
sort(b+1,b+1+n);
int l = b[n/2],r = b[n/2+1];
for(int i=1;i<=n;i++){
if(a[i]>=r){
printf("%.1lf\n",(double)l);
}else{
printf("%.1lf\n",(double)r);
}
}
}else{
memcpy(b,a,sizeof a);
sort(b+1,b+1+n);
int l = b[n/2],r = b[n/2+1];
for(int i=1;i<=n;i++){
if(a[i]>=r){
if(a[i]==r){
printf("%.1f\n",(double)((b[n/2+2]+b[n/2])*1.0)/2);
}else{
printf("%.1f\n",(double)((b[n/2+1]+b[n/2])*1.0)/2);
}
}else{
printf("%.1f\n",(double)((b[n/2+1]+b[n/2+2])*1.0)/2);
}
}
}
return 0;
}
$E-质因数分解$
$哈希表存质因数和出现次数,优先队列交替输出出现次数最大和次大的因子$
$1不是素数,注意特判无解$
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
#define int long long
typedef pair<int,int> PII;
unordered_map<int,int> h;
priority_queue<PII>heap;
int x;
void solve(int n){
h.clear();
int len = 0;
int sum = 0;
for(int i=2;i<=n/i;i++){
int res=0;
while(n%i==0){
n/=i;
res++;
}
if(res!=0)
{
h[i] += res;
}
sum+=res;
len = max(h[i],len);
}
if(n>1) {
h[n] +=1;
len = max(h[n],len);
sum+=1;
}
if(len > (sum+1)/2 || x == 1) cout<<-1<<endl;
else
{
cout<<sum<<endl;
for(auto c:h)
{
if(c.second > 0)heap.push({c.second,c.first});
}
while(!heap.empty())
{
auto t = heap.top();
heap.pop();
cout<<t.second<<' ';
t.first-=1;
if(!heap.empty())
{
auto r = heap.top();
heap.pop();
cout<<r.second<<' ';
r.first-=1;
if(r.first > 0)
{
heap.push({r.first,r.second});
}
}
if(t.first > 0)
{
heap.push({t.first,t.second});
}
}
}
}
signed main()
{
int t;
t = 1;
while(t--){
cin>>x;
solve(x);
}
}