2022 NEERC A、C、N题解

2023/1/10 C++ 算法竞赛 题解 NEERC

被B、L卡死，菜枯

A. Absolutely Flat

题面

如果凳子腿长度都相等，那么直接是可以的

否则可以将腿的长度排个序，垫最短的腿看现在所有凳子腿是否等长

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5];
int main() {
    ios::sync_with_stdio(false);
    int b;
    bool flag=false;
    for(int i=1;i<=4;i++)
        cin>>a[i];
    cin>>b;
    for(int i=1;i<=3;i++)
    {
        if(a[i+1]!=a[i])
        {
            flag=true;
            break;
        }
    }
    if(!flag)
        cout<<1<<'\n';
    else
    {
        sort(a+1,a+1+4);
        a[1]+=b;
        bool flag1=false;
        for(int i=1;i<=3;i++)
        {
            if(a[i+1]!=a[i])
            {
                flag1=true;
                break;
            }
        }
        if(!flag1)
            cout<<1<<'\n';
        else
            cout<<0<<'\n';
    }
    return 0;
}

C. Computer Network

题面

看完题之后给我一种哈夫曼编码的感觉.

尝试用贪心，把延迟最小的接在离终端近的地方.

接完第一层之后再新接入计算机需要接在到根节点路径长最短的节点上面，易证这是最优的.

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int d[N];
int a[N][N];
int deep[N];
int lat[N][N];
int main() {
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    int tmp=n;
    for(int i=1;i<=n;i++)
        cin>>d[i];
    sort(d+1,d+1+n);
    for(int i=1;i<=k;i++)
    {
        a[i][1]=d[i];
        lat[i][1]=d[i];
        deep[i]++;
    }
    tmp-=k;
    int t=k+1;
    while(tmp--)
    {
        int j=1,m=1e9;
        for(int i=1;i<=k;i++)
        {
            if(lat[i][deep[i]]<m)
            {
                j=i;
                m=lat[i][deep[i]];
            }
        }
        deep[j]++;
        a[j][deep[j]]=d[t];
        lat[j][deep[j]]=lat[j][deep[j]-1]+d[t];
        t++;
    }
    /*for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=deep[i];j++)
            cout<<lat[i][j]<<' ';
        cout<<'\n';
    }*/
    int sum=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=deep[i];j++)
            sum+=lat[i][j];
    }
    cout<<sum<<'\n';
    return 0;
}

N. New Time

题面
记个数，纯纯签到题

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int h0,m0;
    char ch;
    cin>>h0>>ch>>m0;
    int h,m;
    cin>>h>>ch>>m;
    int ans=0;
    if(m0<m)
        ans+=m-m0;
    else if(m0>m)
    {
        ans+=60-m0+m;
        h0=(h0+1)%24;
    }
    if(h0<h)
        ans+=h-h0;
    else if(h0>h)
    {
        ans+=24-h0+h;
    }
    cout<<ans<<'\n';
    return 0;
}
img_show