求助贴,求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 湖北

相关推荐

01-23 14:54
同济大学 Java
热爱敲代码的程序媛:给你提几点【专业技能】这个模块里面可优化的地方:1.【具备JVM调优经验】可以去b站上搜一下JVM调优的视频,估计一两个小时凭你的学习能力就能掌握JVM调优的实践方面的技能。2.【MySql优化】MySql这一栏,你去b站或者找个博客看看MySql优化,学一下,如果你本身比较熟悉MySql语句的话,那基本半天时间凭你的学习能力MySql语句优化方面的技能你也能掌握个差不多。以上1,2两点主要是因为我看你专业技能大部分都说的是偏理论,没有写应用。再就是最后,你结合你的项目,想一想你的项目中哪些sql语句是可以用MySql优化的,到时候你面试的时候也好结合着说一下。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务