CF1776D Teamwork

· · 题解

题目简述

有三个人和 a 道简单题，b 道中等难度题和 c 道高难度题。已知做三种题的时间分别为 2,3,4。每个人在一个时间内只能做一道题，且在做一道题的最后一个单位时间要使用超级计算机，一个超级计算机在一个时间内只能给一个人用。问在 l 个时间内他们总共最多能做多少道题，并给出构造方案。

解决方案

枚举在每个时间超级计算机会处理谁的难度为什么的题。优先做难题，优先选择做上到题的时间离现在近的人。

根据贪心思想若能做难题，则一定能做简单题，但能做简单题不一定能做难题，所以能做难题时要先做难题。设一个做上一道题的时间距离现在近的人为 a 人，一个做上一道题的时间距离现在远的人为 b 人，若一道题 a 能做则 b 一定能做，但是一道题 b 能做 a 能做，所以若 a 能做这题则优先选择 a。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long a,b,c,l,cnt;
struct gz{
    long long l,id;
}t[10];
struct tx{
    long long a,b,c;
}ans[1000010];
bool px(gz a,gz b)
{
    if(a.l>b.l) return true;
    if(a.l<b.l) return false;
    return false;
}
signed main()
{
    //freopen("ti.in","r",stdin);
    //freopen("ti.out","w",stdout);
    //ios::sync_with_stdio(0);

    cin>>a>>b>>c>>l;t[1].id=1;t[2].id=2;t[3].id=3;
    for(int i=1;i<=l;i++)
    {
        sort(t+1,t+4,px);
        int tag=0;
        if(c!=0)
        {
            for(int j=1;j<=3;j++)
            {
                if(i-4>=t[j].l)
                {
                    c--;cnt++;
                    ans[cnt].a=t[j].id;
                    ans[cnt].b=i-4;
                    ans[cnt].c=i;
                    t[j].l=i;tag=1;
                    break;
                }
            }
        }
        if(tag==1) continue;
        if(b!=0)
        {
            for(int j=1;j<=3;j++)
            {
                if(i-3>=t[j].l)
                {
                    b--;cnt++;
                    ans[cnt].a=t[j].id;
                    ans[cnt].b=i-3;
                    ans[cnt].c=i;
                    t[j].l=i;tag=1;
                    break;
                }
            }
        }
        if(tag==1) continue;
        if(a!=0)
        {
            for(int j=1;j<=3;j++)
            {
                if(i-2>=t[j].l)
                {
                    a--;cnt++;
                    ans[cnt].a=t[j].id;
                    ans[cnt].b=i-2;
                    ans[cnt].c=i;
                    t[j].l=i;
                    break;
                }
            }
        }
    }
    cout<<cnt<<"\n";
    for(int i=1;i<=cnt;i++) cout<<ans[i].a<<" "<<ans[i].b<<" "<<ans[i].c<<"\n";

    //fclose(stdin);
    //fclose(stdout);
    return 0;
}