求助贴,求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%这个暧昧的数字呢?