牛客周赛 Round 29 （D E)

D E两题出得很好

D.小红的中位数

思路：求中位数肯定要先用一个数组对原数组的数据进行排序， 如果n为偶数，删除其中一位后为奇数，奇数的中位数只有一位，若n为奇数，删除其中一位后为偶数，则中位数由中间两位组成，我们只需讨论删除的数在中位数的左边还是右边，以及是否删掉了中位数这几种情况。

code：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+5;

double a[N],b[N];

int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)
    {
        if(n&1)
        {
            if(a[i]<=b[n/2])
            printf("%.1lf\n",1.0*(b[n/2+1]+b[n/2+2])/2);
            else if(a[i]==b[n/2+1])
             printf("%.1lf\n",1.0*(b[n/2]+b[n/2+2])/2);
            else if(a[i]>=b[n/2+2])
             printf("%.1lf\n",1.0*(b[n/2+1]+b[n/2])/2);
        }
        else
        {
            if(a[i]<=b[n/2])
            printf("%.1lf\n",b[n/2+1]);
            else  printf("%.1lf\n",b[n/2]);
        }
    }
}

E.小红构造数组 

思路 ：先用map将每个质因数出现的次数存一下，然后出现次数多的肯定得先让他跟其他质因数先组合，所以我们可以用priority_queue<PII>从小到大存一下质因数出现的次数。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define int long long
using namespace std;

typedef pair<int,int> PII;

int32_t main()
{
    int x;cin>>x;
    map<int,int> mp;
    if(x==1)
    {
        cout<<-1;
        return 0;
    }
    for(int i=2;i<=x/i;i++)
    {
        while(x%i==0)
        {
            mp[i]++;
            x/=i;
        }
    }
    if(x>1) mp[x]++;
    priority_queue<PII> heap;
    for(auto [a,b]:mp) heap.push({b,a});
    vector<int> res;
    while(heap.size())
    {
        auto [a,b]=heap.top();heap.pop();
        res.push_back(b);
        a--;
        if(heap.size())
        {
            auto [c,d]=heap.top();heap.pop();
            res.push_back(d);
            c--;
            if(c) heap.push({c,d});
        }
        if(a) heap.push({a,b});
    }
    
    for(int i=1;i<res.size();i++)
        if(res[i]==res[i-1])
        {
            cout<<-1;
            return 0;
        }
    cout<<res.size()<<endl;
    for(auto t:res) cout<<t<<' ';
}