免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 4713 | 回复: 24

[算法] 讨论下这几种算法[寻高效的算法] [复制链接]

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-08 14:04 |显示全部楼层
20可用积分
本帖最后由 Susake_ 于 2014-09-09 12:51 编辑

设置成悬赏贴好了(20就封顶了)
下面的数据量就当作10^5处理吧^_^第一楼就用来贴题目!
问题一.有一序列a1,a2,a3,a4......an,查询序列中比ai大的有几个?(一维)------------------------------------------------
输入
5               //有n个数
2 2 3 4 1    //每个数分别为ai
2               //查询次数
2               //第1次
4               //第2次
输出
2              //第一次查询结果
0              //第二次查询结果
问题二.有一个序列数a1,a2,a3,a4......an;查询序列中满足比ai大且比bi大的有几个?(二维)-----------------------------------------
                          b1,b2,b3,b4......bn;
输入
4            //有n组数
1 2         //第i的ai bi      
2 3
1 3
3 5
2          //m次查询
2 3       //第一次
1 2       //第二次
输出
1         //第一次查询结果
2         //第二次查询结果
问题三.有一序列数a1,a2,a3,a4......an;查询序列中满足比ai大且比bi大&&比ci大的有几个?(三维)------------------------------------
                       b1,b2,b3,b4......bn;
                       c1,c2,c3,c4......cn;

....和问题一,二的输入形式差不多~~
问题四.有一系列操作指令,a代表+,d代表-,q代表查询(一维)--------------------------------------------------
输入
6                 //有n次操作指令
a a1 2           //让a1+2          此时a1=2        (所以ai初始状态为0)
a a1 3           //让a1再+3       此时a1=5
a a2 1          //让a2+1           此时a2=1
d a1 1          //让a1-1            此时a1=4
q a1            //查询并输出a1的值    4---------------编辑见下
q a2            //查询兵输出a2的值    1---------------编辑见下
应该是
q a1 a2       //查询a1 a2区间的数的个数   (嗯,这问题的解法是树状数组,同hdc1166)
问题五.大编辑了一下
就是问题二未改动前的模型见5楼
删除了问题6
挺纠结的几个问题,各位有没有好的思路?谢谢哈!!

最佳答案

查看完整内容

呵呵关于第二题你在1楼的描述与6楼原题的描述相差很多。1楼中ai与bi是两个独立因子,两者间没有任何联系。而6楼中它们是作为一个区间的两个边界,这使得两者间存在一个隐含条件:左界小于等于右边界。当然题目可以不设定a必然是左边界、b必然是右边界,这可以在程序中判定并调整为a是左边界、b是右边界。这里就讨论一下6楼原题的解决办法吧,并假定输入的a必然是左边界、b必然是右边界(不假定的情况只需要在读取后调整一下即可) ...

论坛徽章:
1
亥猪
日期:2014-09-10 11:43:17
发表于 2014-09-08 14:04 |显示全部楼层
呵呵关于第二题你在1楼的描述与6楼原题的描述相差很多。

1楼中ai与bi是两个独立因子,两者间没有任何联系。而6楼中它们是作为一个区间的两个边界,这使得两者间存在一个隐含条件:左界小于等于右边界。

当然题目可以不设定a必然是左边界、b必然是右边界,这可以在程序中判定并调整为a是左边界、b是右边界。

这里就讨论一下6楼原题的解决办法吧,并假定输入的a必然是左边界、b必然是右边界(不假定的情况只需要在读取后调整一下即可),而且区间是闭区间。

这时只需要优先按左边界其次按右边界对区间元素进行升序排序,然后分别按左边界和右边界二分检索出两个元素。

那么这两个元素之间的元素必然落入之前检索出的两个边界之内。

这里还需要就闭区间的包含关系说明一下。举例:

两个区间[1, 2]、[1,3],认为是[1,3]包含[1,2]。而两个相同的区间(如[1,2]、[1,2])认为是相互包含的。

下面是实现上面描述的代码。说明的一点是代码中检索左右边界元素时得到的左边界元素为左边界内侧最右边的元素,右边界元素为右边界外侧最左边的元素。

按照6楼描述的输出结果,输出的顺序是与输入区间的顺序对应的,所以排序过程中要带着元素的原索引。

这里我用数组s来存储区间元素,s[0]为原元素索引,s[1]为元素左边界,s[2]为元素右边界。

具体看代码吧。
  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define M(x) (*(int (*)[3])(x))

  4. int cmp(const void * a, const void * b)
  5. {
  6.         return M(a)[1] != M(b)[1] ? M(a)[1] - M(b)[1] : M(a)[2] - M(b)[2];
  7. }

  8. int search(int (*s)[3], int n, int id)
  9. {
  10.         int L, R, i, t;

  11.         for(L = 0, i = n; L < i; s[t=(L+i)/2][1] < s[id][1] ? (L=t+1) : (i=t));
  12.         for(R = 0, i = n; R < i; s[t=(R+i)/2][2] <= s[id][2] ? (R=t+1) : (i=t));
  13.         return R - L - 1;
  14. }

  15. int main()
  16. {
  17.         int (*s)[3], *r, n, i;

  18.         scanf("%d", &n);
  19.         s = (int (*)[3])malloc(sizeof(s[0]) * n);
  20.         r = (int *)malloc(sizeof(r[0]) * n);
  21.         for(i = -1; ++i < n; s[i][0] = i) scanf("%d%d", &s[i][1], &s[i][2]);
  22.         qsort(s, n, sizeof(s[0]), cmp);
  23.         for(i = -1; ++i < n; r[s[i][0]] = search(s, n, i));
  24.         for(printf("%d", r[i = 0]); ++i < n; printf(" %d", r[i]));
  25.         putchar('\n');
  26.         free(s);
  27.         free(r);
  28.         return 0;
  29. }
复制代码
关于第三题待我有时间去CF实际提交一下再说。

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-08 14:20 |显示全部楼层
本帖最后由 Susake_ 于 2014-09-08 15:34 编辑

上面的题目都是自己想的,没有验证地址!
第一题暂时想到的是二分~代码等下补上--[编辑]二分好像也不行,找的目标值不确定!还是直接for吧..--

论坛徽章:
1
亥猪
日期:2014-09-10 11:43:17
发表于 2014-09-08 18:48 |显示全部楼层
本帖最后由 Kurosaki_Ichigo 于 2014-09-08 18:49 编辑

问题一到三是一个问题,排序后二分查找没有问题(一到三只是比较函数不同而已)。当然不能直接用bsearch库函数,需要自己写一个。

问题四按着题意简单顺序操作即可。

问题五我有点疑问,这个区间是个什么概念?针对例子中q a1 b1的输出结果是4,那我下面的例子结果该是什么?

a a1 b2 1
a a2 b2 1
q a1 b2
q a2 b2

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2014-09-08 19:45 |显示全部楼层
终于没看懂楼主在说什么, 题目好像是看懂了, 加上说明就不懂了。
  1. 上面的题目都是自己想的,没有验证地址!
  2. 第一题暂时想到的是二分~代码等下补上--[编辑]二分好像也不行,找的目标值不确定!还是直接for吧..--
复制代码
第123都只能遍历, 题目本身就是要求要遍历的, 最小复杂度都是n,  n-1都不行, 除非成就上仙了果位。

论坛徽章:
0
发表于 2014-09-08 21:05 |显示全部楼层
所有的问题都可以看成数组来处理, 直接对数组进行扫描就可以了.

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-08 21:07 |显示全部楼层
本帖最后由 Susake_ 于 2014-09-09 12:57 编辑

回复 3# Kurosaki_Ichigo
刚刚回复没成功,又重打一遍T_T
先说说前3题
第一题是额外加的
第二题是前段时间碰到的一个问题,但题目的名字忘了
那题的题意是给你n组ai,bi,让你找出比ai大但比bi小的组的个数【反复看了一下好像雷同原先的问题5】
(这里我改成了比ai且比bi大,如果改了题意完全变了那就sorry了)
那题大大意是
先给你4(n)组ai,bi
1 10    即在[1,10]区间的是[2,6],[3,5],[4,7]三组
2 6         在[2,6]区间的是[3,5]
3 5         在[3,5]区间没有
4 7         在[4,7]区间的没有
输出
3 1 0 0
当时看了下数据量比较大,2重for的还是算了,但是排序二分的话,这二维还真不知道该怎么排
第三题是cf12D改的
那题是
给你N个女人的三个指标,如果有一个女人的三个指标都比i女人大,那么i女人就自杀,问总共有多少个女人自杀?
然后自己就想成了,for一下然后只要比i都大的人数>=1就+1,然后就输出结果就行了~
然后就不自觉的问了,这一二三维怎么查最快!- -
另外问题四也打错了,应该是求[a,b]的区间,今天试了一下就是hdu1166敌兵布阵(树状数组AC)~,所以现在删除了问题5和6,- -动大手术了!



   

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-08 22:38 |显示全部楼层
第一题的二分出来了,在找到key的前提下继续前移,由于是降序输出的结果就是答案~
  1. #include <bits/stdc++.h>

  2. int a[5] = {5, 3, 3, 2, 1};

  3. template <class T>
  4. inline T bfind(T r, T key)
  5. {
  6.     T l = 1, m, k, flag = 0;
  7.     while(l != r)
  8.     {
  9.         m = (r + l) / 2;
  10.         if(a[m] > key) l = m + 1;
  11.         if(a[m] < key) r = m - 1;
  12.         if(a[m] == key)
  13.         {
  14.             r = m - 1;
  15.             flag = 1;
  16.             k = m;
  17.             if(a[r] != key) break;
  18.         }
  19.     }
  20.     return flag ? k : -1;
  21. }

  22. int main(int argc, char *argv[])
  23. {
  24.     int key = 1;
  25.     printf("%d\n", bfind(5, key));
  26.         return 0;
  27. }
复制代码

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-09 12:59 |显示全部楼层
第四题开始打错了,现在改成了求区间的值了,正好去试了一下树状数组hdu1166
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <time.h>
  5. #include <string.h>
  6. #include <iostream>
  7. #include <vector>
  8. #include <list>
  9. #include <stack>
  10. #include <queue>
  11. #include <map>
  12. #include <set>
  13. #include <algorithm>

  14. typedef short int int16;///32767
  15. typedef int int32;///2147483647
  16. typedef long long int64;///9223372036854775807
  17. const double PI=acos(-1.0);///3.141593
  18. const long long MOD=(long long)1E9+7LL;///1000000007
  19. int Fibonacci[100]={0,1};///
  20. int Prime[100];///
  21. int Caltan[100];///
  22. template <class T> T Susake_pow(T a,T b)///pow
  23. {T res;if(b==0) return 1;else while((b&1)==0){b>>=1;a*=a;}res=a;b>>=1;while(b!=0){a*=a;if((b&1)!=0)res*=a;b>>=1;}return res;}
  24. template<class T> inline T gcd(T a,T b)///gcd
  25. {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
  26. template<class T> inline T lcm(T a,T b)///lcm
  27. {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
  28. template<class T> inline char *Susake_nsystem(T n)///itoa(26)
  29. {T t=0,i;char *s,*p;s=(char *)malloc(sizeof(char)*1000);p=(char *)malloc(sizeof(char)*1000);
  30. while(n){s[t]=n%26+64;if(s[t]==64){s[t]+=26;n-=26;}t++;n/=26;}s[t]='\0';for(i = 0; i < t; i++)p[i]=s[t-1-i];p[i]='\0';free(s);return p;}
  31. int Susake_system(char *s)///atoi(26)
  32. {int len=strlen(s),i,sum=0;char p[1000];for(i=0;i<len;i++)p[i]=s[len-1-i]-64;for(i=0;i<len;i++)sum+=p[i]*Susake_pow(26,i);return sum;}
  33. int isdigit(int c);int islower(int c);int isupper(int c);
  34. int tolower(int c);int toupper(int c);
  35. ///union_find
  36. int fa[1];
  37. template <class T> inline T union_find(T x)
  38. {return fa[x] == x ? x : fa[x] = union_find(fa[x]);}
  39. ///tree array
  40. int t_a[200001], t_c[200001];
  41. int t_n;
  42. template <class T> inline T lowbit(T x){return x&(-x);}
  43. void update(int p,int x){while(p<=t_n){t_c[p]+=x;p+=lowbit(p);}}
  44. template <class T> inline T sum(T p){T s=0;while(p>0){s+=t_c[p];p-=lowbit(p);}return s;}

  45. int main(int argc, char *argv[])
  46. {
  47.     int t;
  48.     scanf("%d", &t);
  49.     char s[100];
  50.     for(int z = 1; z <= t; z++)
  51.     {
  52.         memset(t_a, 0, sizeof(t_a));
  53.         memset(t_c, 0, sizeof(t_c));
  54.         scanf("%d", &t_n);
  55.         for(int i = 1; i <= t_n; i++)
  56.         {
  57.             t_a[i] += 0;
  58.             update(i, 0);
  59.         }
  60.         for(int i = 1; i <= t_n; i++)
  61.         {
  62.             int x;
  63.             scanf("%d%*c", &x);
  64.             t_a[i] += x;
  65.             update(i, x);
  66.         }
  67.         printf("Case %d:\n", z);
  68.         while(scanf("%s", s))
  69.         {
  70.             if(strcmp(s, "End") == 0) break;
  71.             if(strcmp(s, "Add") == 0)
  72.             {
  73.                 int j, k;
  74.                 scanf("%d%d", &j, &k);
  75.                 t_a[j] += k;
  76.                 update(j, k);
  77.             }
  78.             if(strcmp(s, "Sub") == 0)
  79.             {
  80.                 int j, k;
  81.                 scanf("%d%d", &j, &k);
  82.                 t_a[j] -= k;
  83.                 update(j, -k);
  84.             }
  85.             if(strcmp(s, "Query") == 0)
  86.             {
  87.                 int j, k;
  88.                 scanf("%d%d", &j, &k);
  89.                 printf("%d\n", sum(k) - sum(j - 1));
  90.             }
  91.         }
  92.         getchar();
  93.     }
  94.     return 0;
  95. }
复制代码

论坛徽章:
0
发表于 2014-09-09 15:00 |显示全部楼层
回复 7# Susake_

很显然二分写的不够好。 用线段树也可以解决这个问题吧,如果是动态插入查询,二分就不行了。

   
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP