2016寒假集训队第三次作业（stl）

题解

Probllem A:Moo University - Financial Aid

题意：从C头牛里选N头牛，每头牛有两个属性，得分score和经费aid，在总经费不超过F的情况下使得N头牛的得分中位数最大。

题解：先将C头牛按得分score升序，然后，我们假设每个i都可以作为中位数，a[i].l记录在i之前（也就是分数比它低）的总经费，a[i].r记录在i之后（也就是分数比它高）的总经费，最后，由于是求最大的中位数，所以，得分从后往前循环，第一个满足a[i].l+a[i].y+a[i].r的i就是最优解。在求a[i].l和a[i].r的时候用优先队列把最大值弹出。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int tot,n,c,f;
struct node
{
    int x;
    int y;
    int l;
    int r;
}a[100005];
bool cmp(node a,node b)
{
    return a.x<b.x;
}
int main()
{
    memset(a,0,sizeof(a));
    cin>>n>>c>>f;
    for(int i=1; i<=c; i++)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+1+c,cmp);
    if (n>1)
    {
        priority_queue<int>q;
        int p,t,sum=0;
        for (int i=1; i<=n/2; i++)
        {
            p=a[i].y;
            q.push(p);
            sum+=p;
        }
        for (int i=n/2+1; i<=c-n/2; i++)
        {
            a[i].l=sum;
            p=q.top();
            t=a[i].y;
            if (t<p)
            {
                q.pop();
                q.push(t);
                sum=sum-p+t;
            }
        }
        while (q.size()) q.pop();
        sum=0;
        for (int i=c; i>=c-n/2+1; i--)
        {
            p=a[i].y;
            q.push(p);
            sum+=p;
        }
        for (int i=c-n/2; i>=n/2+1; i--)
        {
            a[i].r=sum;
            p=q.top();
            t=a[i].y;
            if (t<p)
            {
                q.pop();
                q.push(t);
                sum=sum-p+t;
            }
        }
    }
    int ans=-1;
    for (int i=c-n/2; i>=n/2+1; i--)
    {
        tot=a[i].l+a[i].r+a[i].y;
        if (tot<=f)
        {
            ans=a[i].x;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Problem B:Sockets

题意：给出n个电脑，m个电源，电脑有一个值ai,电源有一个值bi，电脑和电源能够配对当且仅当ai=bi。有无穷多个适配器，每对电源用一个适配器bi就减少一半（向上取整）。一个电源可以用很多次适配器。求最多配对多少电脑和电源，以及在最多配对下用的最少的适配器。还要输出方案。

题解：贪心：将电源按照从小到大依次尝试和电脑配对，如果能够配对成功就配对。

证明：假设按照这个顺序配对会使得配对数减少，也就是说有一个比他大的电源本应该和这个电脑相配。因为这两个电源都匹配到了这个电脑，所以当前枚举的电源往下能够匹配的电脑也能被那个比他大的电源匹配掉。

参考代码：

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
int n,m,c,u,x;
int s[200005],a[200005],b[200005];
multimap<int,int> p;
int main()
{
    memset(a,-1,sizeof(a));
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        cin>>x;
        p.insert(make_pair(x,i));
    }
    for (int i=1; i<=m; i++)
        cin>>s[i];
    for (int i=0; i<=30; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (a[j]==-1)
            {
                multimap<int,int>::iterator t=p.find(s[j]);
                if (t!=p.end())
                {
                    a[j]=i;
                    b[t->second]=j;
                    c++;
                    u+=i;
                    p.erase(t);
                }
            }
        }
        for (int j=1; j<=m; j++)
        {
            if (s[j]%2==1) s[j]=s[j]/2+1;
            else s[j]=s[j]/2;
        }
    }
    cout<<c<<" "<<u<<endl;
    for( int i=1; i<=m; i++)
    {
        if (a[i]==-1)
            cout<<0<<" ";
        else cout<<a[i]<<" ";
    }
    cout<<endl;
    for(int i=1; i<=n; i++)
        cout<<b[i]<<" ";
    cout<<endl;
    return 0;
}

Problem C:HDU Today

题意：最短路径问题。

题解：把相对应的字符串转化一下，其中的信息存储到二维数组中，然后用迪杰斯特拉算法求解就行了。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[155][155],f[155],k,minn,p,n,a,b,x,j,ans;
bool bo[155];
char s1[155],s2[155],na[155][155];
int dijkstra(int v)
{
    for (int i=0; i<k; i++)
    {
        bo[i]=0;
        f[i]=map[v][i];
    }
    bo[v]=1;
    f[v]=0;
    for (int i=0; i<k; i++)
    {
        minn=100000000;
        for (int j=0; j<k; j++)
            if (bo[j]==0 && minn>f[j])
            {
                minn=f[j];
                p=j;
            }
        if (minn==100000000) break;
        bo[p]=1;
        for (int j=0; j<k; j++)
            if (bo[j]==0 && f[j]>(f[p]+map[p][j]))
                f[j]=f[p]+map[p][j];
    }
    return f[1];
}
int main()
{
    while (cin>>n)
    {
        if (n==-1) break;
        for (int i=0; i<155; i++)
            for (int j=0; j<155; j++)
                map[i][j]=100000000;
        cin>>na[0]>>na[1];
        k=2;
        for (int i=0; i<n; i++)
        {
            cin>>s1>>s2>>x;
            for (j=0; j<k; j++)
                if (strcmp(s1,na[j])==0)
                {
                    a=j;
                    break;
                }
            if (j==k)
            {
                strcpy(na[k],s1);
                a=k;
                k++;
            }
            for (j=0; j<k; j++)
                if (strcmp(s2,na[j])==0)
                {
                    b=j;
                    break;
                }
            if (j==k)
            {
                strcpy(na[k],s2);
                b=k;
                k++;
            }
            if (map[a][b]>x) map[a][b]=x;
            if (map[b][a]>x) map[b][a]=x;
        }
        if (strcmp(na[0],na[1])==0) cout<<0<<endl;
        else
        {
            ans=dijkstra(0);
            if (ans>=100000000) cout<<-1<<endl;
            else cout<<ans<<endl;
        }
    }
    return 0;
}

Problem F:Pearls in a Row

题意：把一段项链，分成多小段，每一小段至少存在两个相同的类型的珍珠，求最多能分成多少段，如果不能分，则输出-1。

题解：用map记录当前一段某类型的珍珠是否出现过，如果当前珍珠的类型已出现过，则将其与前面的珍珠分成一段。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<set>
using namespace std;
int n,a[300005],k,x;
set<int> s;
int main()
{
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>x;
        if (s.count(x)==0) s.insert(x);
        else
        {
            a[k]=i;
            k++;
            s.clear();
        }
    }
    //for (int i=0; i<k; i++)
    //    cout<<a[i]<<endl;
    //cout<<endl;
    if (k==0) cout<<-1<<endl;
    else
    if (k==1)
    {
        cout<<k<<endl;
        cout<<1<<" "<<n<<endl;
    }
    else
    {
        cout<<k<<endl;
        cout<<1<<" "<<a[0]<<endl;
        for (int i=0; i<k-2; i++)
            cout<<a[i]+1<<" "<<a[i+1]<<endl;
        cout<<a[k-2]+1<<" "<<n<<endl;
    }
    return 0;
}