Codeforces Round #251 (Div. 2)-C,D_html/css_WEB-ITnose

Question C:

The idea is very simple.

It can be seen from the meaning of the question that there are k-p sets of odd numbers and p even-numbered geometries.

Then we first select k-p-1 odd numbers, each odd number is a set.

Then we select p even numbers. Each even number is a set. If the number of even numbers is insufficient, then use two odd numbers to make up for it.

Then we put all the remaining numbers into a set.

By rowanhao, contest: Codeforces Round #251 (Div. 2), problem: (C) Devu and Partitioning of the Array, Accepted, # #include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<vector>#include<queue>using namespace std;#define LL __int64#define maxn 330000vector<int>vec;int a[maxn];int vis[maxn];int main(){    int n,k,p;    while(~scanf("%d%d%d",&n,&k,&p))    {        int sum=0;        int q=k-p;        int l,r;        l=r=0;        for(int i=1;i<=n;i++)        {            scanf("%d",&a[i]);            if(a[i]%2)            {                sum++;                if(r<q)r++;                else l+=1;            }            else l+=2;        }        memset(vis,0,sizeof(vis));        if(r==q&&l>=p*2&&l%2==0)        {            l=p;            cout<<"YES"<<endl;            if(p==0)r--;            for(int i=1;i<=n;i++)            {                if(a[i]%2&&r)                {                    r--;                    printf("1 %d\n",a[i]);                    vis[i]=1;                }                if(a[i]%2==0&&l>1)                {                    vis[i]=1;                    l--;                    printf("1 %d\n",a[i]);                }            }            vec.clear();            for(int i=1;i<=n;i++)            {                if(vis[i])continue;                vec.push_back(a[i]);                if(l>1&&vec.size()==2)                {                    printf("2 %d %d\n",vec[0],vec[1]);                    vec.clear();                    l--;                }            }            if(vec.size()==0)continue;            printf("%d",vec.size());            for(int i=0;i<vec.size();i++)printf(" %d",vec[i]);            puts("");        }        else cout<<"NO"<<endl;    }    return 0;}

Question D:

The idea is quite simple.

From the meaning of the question, we need to make all the numbers in the a array greater than or equal to x. All numbers in array b are less than or equal to x.

x is a number in array a and array b.

Then we enumerate x and then perform a binary search.

#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<vector>using namespace std;#define LL __int64#define maxn 220100double num[maxn];vector<LL>vec;LL a[maxn];LL b[maxn];LL sa[maxn];LL sb[maxn];LL n,m;LL dos(LL x){    LL sum=0;    LL l,r,mid;    l=1;r=n+1;mid=(l+r)/2;    while(l<r)    {        if(a[mid]>=x)r=mid;        else l=mid+1;        mid=(l+r)/2;    }    sum+=(mid-1)*x-sa[mid-1];    l=1;r=m+1;mid=(l+r)/2;    while(l<r)    {        if(b[mid]>=x)r=mid;        else l=mid+1;        mid=(l+r)/2;    }    sum+=sb[mid]-(m-mid+1)*x;    return sum;}int main(){    while(~scanf("%I64d%I64d",&n,&m))    {        for(LL i=1;i<=n;i++)        {            scanf("%I64d",&a[i]);            vec.push_back(a[i]);        }        for(LL i=1;i<=m;i++)        {            scanf("%I64d",&b[i]);            vec.push_back(b[i]);        }        sort(a+1,a+n+1);        sort(b+1,b+m+1);        sort(vec.begin(),vec.end());        memset(sa,0,sizeof(sa));        memset(sb,0,sizeof(sb));        for(LL i=1;i<=n;i++)sa[i]=sa[i-1]+a[i];        for(LL i=m;i>=1;i--)sb[i]=sb[i+1]+b[i];        LL  minn=-1;        for(LL i=0;i<vec.size();i++)        {            LL  x=vec[i];            if(minn==-1)minn=dos(x);            else minn=min(minn,dos(x));        }        cout<<minn<<endl;    }    return 0;}