排序+贪心错在哪了

/*
 * 最优比第一次尝试:按p/r排序 
 * 最优比第二次尝试:(a.r+b.r)*b.p + a.r*a.p < (a.r+b.r)*a.p + b.r*b.p (a先做的消耗小于b先做的消耗)
 */

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 50 + 5;

struct node
{
    int max;        //分数 
    int poi;        //每分钟减少的分数 
    int req;        //花费的时间 
    double opt;        //最优比 
}arr[maxn];

int n, t;
long long ans = 0;
long long cnt = 0;

bool cmp(node a, node b)
{
    if(a.opt == b.opt)
    {
        if(a.max == b.max) return a.req < b.req;
        else return a.max > b.max;
    }
    else return a.opt > b.opt;
}

int main()
{
    //1 输入
    //1.1 第一行输入两个整数N,T (1 ≤ N ≤ 50, 1 ≤ T ≤ 100000) 
    scanf("%d%d", &n, &t);
    //1.2 第二行输入n个整数maxPoints[i]
    for(int i = 1; i <= n; i++)
        scanf("%d", &arr[i].max);
    //1.3 第三行输入n个整数pointsPerMinute[i]
    for(int i = 1; i <= n; i++)
        scanf("%d", &arr[i].poi);
    //1.4 第四行输入n个整数requiredTime[i]
    for(int i = 1; i <= n; i++)
        scanf("%d", &arr[i].req);
    
    //2 按最优比排序 
    //2.1 求最优比
    for(int i = 1; i <= n; i++)
        arr[i].opt = 1.0 * arr[i].poi / arr[i].req;
    //2.2 按最优比由大到小排序 
    sort(arr + 1, arr + n + 1, cmp);
    
    //3 贪心求最大分值 
    long long temp;
    for(int i = 1; i <= n; i++)
    {
        //3.1 求这道题的最终得分 
        //3.1.1 如果这道题做不完,直接跳过
        if(cnt + arr[i].req > t) continue;
        //3.1.2 否则能做完,做一下试试 
        temp = arr[i].max - arr[i].poi * (cnt + arr[i].req);
        //3.2 如果最终得分为正,则做这道题,否则不做 
        if(temp > 0)
        {
            ans += temp;
            cnt += arr[i].req;
        }
    }
    
    //4 输出最大分值
    printf("%lld\n", ans);
    
    return 0;
}

全部评论
本题貌似没有贪心策略
点赞 回复
分享
发布于 2019-11-11 19:34
排完序还要dp
点赞 回复
分享
发布于 2019-11-11 19:39
联易融
校招火热招聘中
官网直投
贪心不能保证全局最优,而且这个贪心还没考虑全,比如 n = 2,T = 2;Q1: 6 4 2;Q2: 5 1 2 答案就不对了
点赞 回复
分享
发布于 2020-02-02 16:53

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务