枚举+贪心 hdu-4334-Trouble - c++编程基础

TOP

枚举+贪心 hdu-4334-Trouble

2014-11-23 20:10:36 来源: 作者: 【大中小】浏览:17次

Tags：枚举贪心 hdu-4334-Trouble

题目意思：

给5组数，每组含n个数（n<=200),在5组数中各选一个，问是否存在一种组合使这5个数的和为0。

解题思路：

这题数据很强，o(n^3*lgn过不了）

对于在两组数各选一个使得和为定值，有一种贪心的算法，时间复杂度为（n*lgn,实际上就是排序的算法时间复杂度)。

所以可以把第二组和第三组数合并组合40000个数作为第二组，第四组和第五组合并成40000个数作为第三组。

分别排序。

1、然后枚举第一组，初始时用p指针指向第二组中的第一个数，q指针指向第三组的最后一个数，以第二组为基准。

2、当三数大于0时，说明q指针后面的所有数与p指针后面的数肯定不行，大于当前的和值，同时说明p指针后面的只可能和q指针前面的凑，所以q指针往前移。

3、当三数小于0时，说明p与当前的q不行，p与q后面的也不行（由上一步得），p与q前面的更不行。所以p只能往后移。

贪心思想，所以最多只移动了40000+40000次。

所以总的时间复杂度为o(n^3).

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
ll s1[41000],s2[41000];
ll sa[6][210];
int cnt1,cnt2,n;

int main()
{
   int t;

   scanf("%d",&t);
   while(t--)
   {
      scanf("%d",&n);
      for(int i=1;i<=5;i++)
         for(int j=1;j<=n;j++)
            scanf("%I64d",&sa[i][j]);
      //sort(sa[1]+1,sa[1]+n+1);
      cnt1=cnt2=0;
      for(int i=1;i<=n;i++) 
         for(int j=1;j<=n;j++)
         {
            s1[++cnt1]=sa[2][i]+sa[3][j]; //把2、3组合并和把4、5组合并
            s2[++cnt2]=sa[4][i]+sa[5][j];
         }
      sort(s1+1,s1+cnt1+1);
      sort(s2+1,s2+cnt2+1);
      
      int t=1; //离散化一下，去掉相同的
      for(int i=2;i<=cnt1;i++)
         if(s1[i]!=s1[i-1])
            s1[++t]=s1[i];
      cnt1=t;
      t=1;
      for(int i=2;i<=cnt2;i++)
         if(s2[i]!=s2[i-1])
            s2[++t]=s2[i];
      cnt2=t;

     /* if(sa[1][n]+s1[cnt1]+s2[cnt2]<0)
      {
         printf("Yes\n");
         continue;
      }*/
      bool ans=false;
      for(int i=1;i<=n&&!ans;i++)
      {
         //if(sa[1][i]+s1[1]+s2[1]>0)
          //  break;
         for(int p=1,q=cnt2;p<=cnt1&&q>=1;) //贪心思想
         {
            ll tt=sa[1][i]+s1[p]+s2[q];
            if(tt==0)
            {
               ans=true;
               break;
            }
            else if(tt>0)
               q--;
            else
               p++;
         }
      }
      if(ans)
         printf("Yes\n");
      else
         printf("No\n");
   }

   return 0;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ1947：Rebuilding Roads(树形D..	下一篇：设计模式之桥接模式C++简单实现

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: