信息学奥赛一本通T1426-智力大冲浪(题型)

解题思路:

首先，从输入中获取任务截止日期m和任务数量n。

然后，使用一个循环，依次获取每个任务的截止日期和罚款金额，并将其存储在结构体数组a中。

接下来，使用sort函数对结构体数组a进行排序，排序的依据是罚款金额从大到小。这样做是为了优先处理罚款金额较大的任务，以最大程度地减少罚款金额。

然后，定义一个标志变量flag和一个长度为500的数组f，用于记录每个日期是否有任务安排。初始时，flag设为1，表示没有找到空闲时间。

接下来的循环中，从当前任务的截止日期开始，逆序遍历日期，寻找空闲时间。如果找到空闲时间，则将对应日期的f值设为1，并将flag设为0，表示找到了空闲时间。

如果flag仍为1，表示前面的日期已经排满，无法找到空闲时间。此时，需要罚款。将m减去当前任务的罚款金额。

最后，输出剩余的m，即能够处理的最大任务数量。

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

struct node

{

    int t,cost;

}a[500];

bool cmp(node a,node b){return a.cost>b.cost;}

int m,n,flag;

int f[500]={0};

int main()

{

    cin>>m>>n;

    for(int i=1;i<=n;i++)cin>>a[i].t;

    for(int i=1;i<=n;i++)cin>>a[i].cost;

    sort(a+1,a+n+1,cmp);

    for(int i=1;i<=n;i++)

    {

        flag=1;

        for(int j=a[i].t;j>=1;j--)

        {

            if(f[j]==0)

            {

                f[j]=1,flag=0;

                break;

            }

        }

        if(flag==1)m-=a[i].cost;

    }

    cout<<m;

    return 0;

}

先按钱数从大到小排序，

第一步，先取最大cost，从其截止时间往后向1走，找空位；

同理，第二步，取第2的cost，从其截止时间向1走，找空位，其间，第2个cost的截止时间可能大于或小于第一个的截止时间，但结果的一样。

如果位置被站满了，只能扣钱了。