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

相关推荐

10-24 13:36
门头沟学院 Java
Zzzzoooo:更新:今天下午有hr联系我去不去客户端,拒了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务