求助贴,求dalao们随便看一眼。NC25043,保护花朵

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<bitset>
#include<cmath>
using namespace std;
const int maxn=1e5+7;
struct tt
{
    int z,r;//整数,余数
     long long t,d;
}ans[maxn];
bool cmp(tt a,tt b)//贪心排序
{
    if(a.z!=b.z)return a.z<b.z;
    return a.r<b.r;
}
int main()
{
    int n;cin>>n;int x,y;
    for(int i=1;i<=n;i++)
    {
        scanf(" %d%d",&ans[i].t,&ans[i].d);
        x=ans[i].t,y=ans[i].d;
        ans[i].z=x/y;ans[i].r=x%y;
    }
    sort(ans+1,ans+1+n,cmp);
    long long time=0;long long an=0;
    for(int i=1;i<=n;i++)
    {
        an+=time*ans[i].d;
        time+=ans[i].t*2;
    }
    cout<<an;
    
    return 0;
}

将题中贪心排序部分改为下面这个就对了

bool cmp(tt a,tt b)
{
    return a.t*b.d<b.t*a.d;
}

那么我有一个疑问,我已经推出来贪心排序的式子了,A(t)*B(d)<B(t)*A(d),等价于A(t)/A(d)<B(t)/B(d),全部数字均为正整数,没发现什么除数为零等特殊情况。我将每一个式子(t)/(d)拆分为整数和余数,排序函数写的也是整数优先比较,再比余数。既然这样,为什么明明相同的排序,通过率只有33.3%这个暧昧的数字呢?

全部评论
举个栗子a.t = 2,a.d = 1000000,和b.t = 1, d = 2,你的代码会先运b牛,但先运a牛才是最优解。
1 回复 分享
发布于 2023-07-24 19:54 江西
确实不太容易往这方面想,看了挺久才发现
1 回复 分享
发布于 2023-07-24 19:56 江西
谁告诉你这样比较的画蛇添足啊
点赞 回复 分享
发布于 2023-07-24 10:36 湖北

相关推荐

hso_:哈哈哈哈哈哈我没offer一样在同一道题开喷了
投递深圳同为数码等公司10个岗位
点赞 评论 收藏
分享
11-09 14:54
已编辑
华南农业大学 产品经理
大拿老师:这个简历,连手机号码和照片都没打码,那为什么关键要素求职职位就不写呢? 从上往下看,都没看出自己到底是产品经理的简历,还是电子硬件的简历? 这是一个大问题,当然,更大的问题是实习经历的描述是不对的 不要只是去写实习流程,陈平,怎么去开会?怎么去讨论? 面试问的是你的产品功能点,是怎么设计的?也就是要写项目的亮点,有什么功能?这个功能有什么难处?怎么去解决的? 实习流程大家都一样,没什么优势,也没有提问点,没有提问,你就不得分 另外,你要明确你投的是什么职位,如果投的是产品职位,你的项目经历写的全都是跟产品无关的,那你的简历就没用 你的面试官必然是一个资深的产品经理,他不会去问那些计算机类的编程项目 所以这种四不像的简历,在校招是大忌
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务