注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2008Moo University - Team Tryouts题解  

2014-03-31 22:24:06|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                      sd 
                                          BY   LGS
题目大意;给出N个奶牛,求最多的K个奶牛,使得k个奶牛中每个奶牛i满足A*(H[I]-h)+B*(W[I]-w)《=c。A,B,C给定。

题解:太神了。首先A*(H[I]-h)+B*(W[I]-w)《=c等于    A*H[I]+B*W[I]<=C+A*H+B*W
一个O(N^3)的解法:枚举最小h,最小w,再O(N)扫一遍。于是我们想优化,对于o(N)的扫描能否能成O(1)呢。当两个h,w以定住,那么如果我们将A*h【i】+B*W[I]排个序,因为它们都是定值。然后再对W排序,因为枚举最小W[J]是递增的,且A*H[I]+B*W[I]也是递增的,所以枚举可以从上面的继承过来。因为如果上一个X*H[I]+B*W[I]《=C+A*H+B*W,现在W变大,X一定任然满足条件的。而对于W数组,由于枚举最小的W增大J+1了,那么扫的奶牛必须得在J+1,J位置的奶牛个数必须清掉,用个类似hash记录,再减去就行了。

总结:数论,太强了。
代码:
  • Source Code
  • #include<cstdio>
    #include<algorithm>
    #define maxn 2000
    #define maxx 200000
    using namespace std;
    struct node{int h,w,k;}g[maxn];
    int i,j,n,k,m,ans,tem,minh,minw,l,v,f[maxx],a,b,c,h[maxn],w[maxn];
    bool cmp(const node&a,const node&b){return (a.k<b.k);}
    int main()
    {
     scanf("%d",&n);
     scanf("%d%d%d",&a,&b,&c);
     for (i=1;i<=n;i++)
      {scanf("%d%d",&g[i].h,&g[i].w);
       g[i].k=a*g[i].h+b*g[i].w;
       h[i]=g[i].h;w[i]=g[i].w;
      }
    sort(g+1,g+n+1,cmp); 
    sort(h+1,h+n+1);sort(w+1,w+n+1);
    for (i=1;i<=n;i++)
            {
            if (i>1&&h[i]==h[i-1])continue;
            minh=h[i];
            l=1;v=c+a*minh;tem=0;
      for (j=1;j<=n;j++)
             {
             if (j>1&&w[j]==w[j-1])continue;
             minw=w[j];
             v+=b*minw;
             for (;l<=n;l++)
               {
               if (g[l].k>v)break;
               if (g[l].h<minh||g[l].w<minw)continue;
               f[g[l].w]++;tem++;
               }
             if (j>1)tem-=f[w[j-1]];f[w[j-1]]=0;
             if (tem>ans)ans=tem;
             v-=b*minw;
             }
            }
      printf("%d\n",ans);
      return 0;
    }
    

  评论这张
 
阅读(1317)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018