CCF-CSP第41次认证第二题——机器人项目管理

题目描述

小 P 计划招募 n 个机器人完成一个项目：每个机器人负责其中的一项任务，编号从 1 到 n，任务之间互不干扰。如果完成任务 i 的耗时为 tit，则该项目总耗时为 t1+t2+⋯+tn。

作为项目管理者，小 P 可以用有限的预算为机器人们购买咖啡加油。其中负责任务 ii 的机器人，最多可以喝 ai 杯咖啡，从而将该任务耗时缩短 bibi（最终耗时即为 ti−bi）。

根据任务的特性和机器人的偏好，n 项任务可分为“灵活型”和“普通型”两类，详情参见附件资料（重要）。

已知小 P 可以为机器人们提供最多 mm 杯咖啡，试计算完成整个项目的最短时间。

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 n 和 m，分别表示任务数量和咖啡数量。

接下来 n 行，每行包含空格分隔的四个整数 oi、ti、ai 和 bi，表示一个任务。其中 oi∈{0,1} 表示任务类别，oi=0 表示灵活型、oi=1 表示普通型；其余变量含义如上所述，输入数据保证 ti>bi，即缩短后的耗时仍大于零。

输出格式

输出到标准输出。

输出一个实数，表示完成整个项目的最短时间。

样例1输入

样例1输出

6.6

样例1解释

三个任务均为灵活型，初始总耗时为 2+3+4=9。最优方案为：给任务二分配 4 杯咖啡，耗时缩短 2；给任务三分配 11 杯咖啡，耗时相应缩短 25=0.4。综上，完成整个项目最短时间为 9−2−0.4=6.6。

样例2输入

5 62
0 10 2 1
0 10 1 1
1 500 40 360
1 600 50 500
1 400 20 150

样例2输出

1008.5

样例2解释

初始总耗时为 1520。最优方案为：给任务三分配 40 杯咖啡，耗时缩短 360；给任务五分配 20 杯咖啡，耗时缩短 150；给任务一和二各分配 1 杯咖啡，耗时分别缩短 0.5 和 1。综上，完成整个项目最短时间为 1520−360−150−0.5−1=1008.5。

子任务

80% 的测试点满足：所有任务均为灵活型任务，且对于每个任务 i 有 0<ai≤20；

全部的测试点满足：0<n≤200、0<m≤1000，且对于每个任务 ii 有 0<ai≤100、0<bi<ti≤104。

评分方式

输出结果与标准答案相比绝对误差小于 0.001 即可，推荐保留六位小数输出结果。

题解

基础的背包问题，单纯的01背包，需要把灵活型的咖啡拆成一杯一杯的再存入候选项中，最后用01背包做就行，这道题好像没有卡复杂度，直接拆就行，不用二进制优化。

0-1背包模版

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}

代码如下

#include<bits/stdc++.h>

using namespace std;

const int N=210,M=1010;
int n,m,o,t,a[N],sum,cnt;
double b[N],dp[M];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>o>>t>>a[cnt]>>b[cnt];
        sum+=t;
        if(o==0){
            int temp=cnt;
            for(int j=1;j<a[temp];j++){
                a[++cnt]=1;
                b[cnt]=b[temp]/(double)a[temp];
            }
            b[temp]=b[temp]/(double)a[temp];
            a[temp]=1;
        }
        cnt++;
    }
    for(int i=0;i<cnt;i++)
        for(int j=m;j>=a[i];j--)
            dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
    cout<<sum-dp[m]<<endl;
}

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2501_92845263/article/details/159642932