HDU 1425 Hash求解

男娘i 2024-02-17 18:53 53阅读 0赞

本题用快排也可以过 （时间复杂度（nlgn））； Hash 时间复杂度 n;

快排：

1.  \#include<cstdio>
2.  \#include<algorithm>
3.  using namespace std;
4.  const int maxn=1000000+10;
5.  int a\[maxn\];
6.  bool cmp(int a,int b)\{return a>b;\}
7.  int main()\{ 
8.   int n,m;
9.   while(scanf("%d%d",&n,&m)==2)\{ 
10.  for(int i=0;i<n;i++)scanf("%d",&a\[i\]);
11.  sort(a,a+n,cmp);
12.  printf("%d",a\[0\]);
13.  for(int i=1;i<m;i++)printf(" %d",a\[i\]);
14.  printf("\\n");
15.  \}
16.  return 0;
17. \}

Hash:

1.  \#include<cstdio>
2.  \#include<cstring>
3.  const int maxn=1000000+10;
4.  int hash\[maxn\];
5.  int main()\{ 
6.   int n,m;
7.   while(scanf("%d%d",&n,&m)==2)\{ 
8.   memset(hash,0,sizeof(hash));
9.   for(int i=0;i<n;i++)\{ 
10.  int temp;
11.  scanf("%d",&temp);
12.  hash\[500000+temp\]=1; 
13.  \}
14.  int t=m;
15.  for(int i=maxn-1;m>0;i--)\{ //有一点不清楚的是这里不能写出 i=sizeof(hash)-1;????
16.  if(hash\[i\])\{ 
17.  if(m==t)
18.  printf("%d",i-500000);
19.  else printf(" %d",i-500000);
20.  m--;
21.  \}
22.  \}
23.  printf("\\n");
24.  \}
25.  return 0;
26. \}

练习本题的目的是学会运用Hash求解问题。

发表评论取消回复

表情：

评论列表（有 0 条评论，53人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1425 Hash求解

本题用快排也可以过（时间复杂度（nlgn））； Hash 时间复杂度 n; 快排： 1. \include<cstdio> 2. \include<algo

男娘i/ 2024年02月17日 18:53/ 0 赞/ 54 阅读

相关 HDU 杭电 1496 （Hash求解）

看到这题首先想到的是四重for循环，肯定超时，但还是很想试一下，结果和预期一样；然后就换成三重循环，结果还是超时；最后就换成 hash求解（第一次接触）两重循环。由题意可得a\

小咪咪/ 2024年02月17日 18:53/ 0 赞/ 28 阅读

相关 hdu 1425

题意：给你n个整数，请按从大到小的顺序输出其中前m大的数哈希表写法：这个也相当于是暴力写，一般暴力写我们输入输出就采用scanf,printf，否则很容易超时 Pre

桃扇骨/ 2023年08月17日 16:26/ 0 赞/ 88 阅读

相关 HDU 1280(HASH)

include <cstdio> include <cstring> include <climits> define N 3

我就是我/ 2022年09月20日 12:43/ 0 赞/ 137 阅读

相关 HDU 5469 Antonidas【点分治+hash】

首先将串的前缀和后缀分别hash。然后用树分治。对于树分治，每一个分治的root，我们首先要加上经过root的串匹配出的答案，其次要减去v→root→v这样的串（不合

痛定思痛。/ 2022年08月08日 20:00/ 0 赞/ 149 阅读

相关 HDOJ 1425-sort

sort Time Limit: 6000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

向右看齐/ 2022年07月26日 00:06/ 0 赞/ 113 阅读

相关 hdu 1425 sort

sort Time Limit: 6000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

￡神魔★判官ぃ/ 2022年05月31日 08:45/ 0 赞/ 143 阅读

相关 HDU 1686Oulipo ———————Hash or KMP

Oulipo Oulipo Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/3

雨点打透心脏的1/2处/ 2022年05月16日 08:23/ 0 赞/ 156 阅读

相关 HDU-4821-String-hash-map

-------------------- title: HDU 4821 String --hash+map date: 2018-10-30 10:30:03 c

太过爱你忘了你带给我的痛/ 2022年04月22日 02:06/ 0 赞/ 158 阅读

相关 1425 hash

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] Code \include <stdio.h> \inclu

╰半夏微凉°/ 2022年01月09日 05:55/ 0 赞/ 186 阅读