[数据结构与算法]2022牛客寒假算法基础集训营1

E

炸鸡块君的高中回忆

题意：n个人进学校，m个人带了校园卡，先让m个人带校园卡进入学校，再派一个人带着所有m张校园卡出来，重复上述过程，直到所有人进入学校。进出都需要花费一个单位时间，问共花费多少时间

思路：首先n>1&&m==1时无法全部进入，若n<=m,则只需花费1分钟，当n>m时，只能分多批进入。一批相当于只进入了m-1个人，进行i轮进m出1后，还剩下n-i*(m-1)人，当剩下的人数小于等于m时，即i>=(m-n)/(1-m),(注意，i为轮数需要向上取整)? ?最后一批（花费1时间）可以全部进入。共花费2*i+1时间.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e6 + 10;
ll t, n, m;
void solve()
{
    scanf("%lld %lld", &n, &m);
    if (n > 1 && m == 1)
        printf("-1\n");
    else
    {
        if (n <= m)
            printf("1\n");
        else if (n > m)
        {
            ll i=(double)(1.0*m-n)/(1.0-m);
            if((m-n)%(1-m)!=0) i++;//向上取整
            ll ans=i*2+1;
            printf("%lld\n",ans);
        }
    }
}
int main()
{
    scanf("%lld", &t);
    while (t--)
    {
        solve();
    }
    system("pause");
}

J

小朋友做游戏

题意：A个安静的小朋友和B个闹腾的小朋友，选n个小朋友围成圈做游戏，但闹腾小朋友不能相邻，给定每个小朋友的幸福度，求出最大幸福度

思路：先将两组幸福度进行降序排序分别叫做arr和brr数组。如果选定安静小朋友人数<选定的闹腾小朋友的人数则不能进行游戏，否则最优方案一定是从arr和brr中各取一个前缀和。因此可以求出两个数组的前缀和，然后枚举从A组中选了多少人（从 B中选的人数等于总人数n减去A中的），利用前缀和𝑂(1)的获得此时的总幸福度。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e4 + 10;
ll t,n,A,B;
ll arr[maxx],brr[maxx];
ll sa[maxx],sb[maxx];
bool cmp(ll a,ll b)
{
    return a>b;
}
void solve()
{
    ll ret=0,ans=-0x3f3f3f3f;
    scanf("%lld %lld %lld",&A,&B,&n);
    for(ll i=1;i<=A;i++) scanf("%lld",&arr[i]);
    for(ll i=1;i<=B;i++) scanf("%lld",&brr[i]);
    sort(arr+1,arr+A+1,cmp);
    sort(brr+1,brr+B+1,cmp);
    for(ll i=1;i<=A;i++) sa[i]=sa[i-1]+arr[i];
    for(ll i=1;i<=B;i++) sb[i]=sb[i-1]+brr[i];
    ll tem=0;
    if(n%2==0) tem=n/2;//i>=n-i控制i的下界
    else tem=n/2+1;//n为奇数时会向下取整，所以要+1
    for(int i=min(A,n);i>=tem;i--)//注意i从A和n的最小值开始枚举
    {
        if(n-i>B||n-i>i) continue;//选中B组人数n-i大于B组总人数||闹腾人数>安静人数
        ret=sa[i]+sb[n-i];
        ans=max(ans,ret);
    }
    if(ans<0) printf("-1\n");
    else printf("%lld\n",ans);

}
int main()
{
    scanf("%lld",&t);
    while (t--)
    {
        solve();
    }
    system("pause");
}