希望思路可以具体一点,或者帮敲一下,参考一下
1条回答 默认 最新
- 赵4老师 2021-11-05 10:08关注
//现在假定敌方军队有n支小队,假定第i支小队的位置在(i,f[i])。 //平安将军需要找到重点打击区域以进行火炮攻击,因此需要找到哪个区域军队小队数量最多。现在有m个查询,为了简化问题每个查询有一个矩形,你需要计算每一个矩形内有多少行有小队。 //Input // 第一行包括一个整数T(T<=5)代表数据组数。 // 对于每组数据: // 第一行包含两个整数 n,m(1<=n<=1e5,1<=m<=1e5),分别表示小队个数和查询次数。 // 第二行包含n个整数 f[i](0<=f[i]<=1e5)。 // 接下来m行,每行包含四个整数 x0,y0,x1,y1(1<=x0,x1<=n,0<=y0,y1<=1e5),代表该两点确定下的矩形。 //Output // 对于每个查询,打印一个整数代表该区域内有多少行有小队。 //Sample Input // 1 // 4 2 // 1 0 3 1 // 1 0 4 3 // 1 0 4 2 //Sample Output // 3 // 2 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #define MAX 100000 #define ROWS (MAX+1) #define BYTES_PER_ROW ((MAX+1)/8+1) #define TOTAL_BYTES ROWS*BYTES_PER_ROW char *map; int T,n,m,t,i,fi,y,x,x0,y0,x1,y1,r; int main() { map=(char *)malloc(TOTAL_BYTES); if (NULL==map) { printf("Can not malloc %d bytes!\n",TOTAL_BYTES); return 1; } scanf("%d",&T); for (t=0;t<T;t++) { memset((void *)map,0,TOTAL_BYTES); scanf("%d%d",&n,&m); for (i=1;i<=n;i++) { scanf("%d",&fi); map[fi*BYTES_PER_ROW+i/8]|=(1<<(i%8)); } for (i=0;i<m;i++) { scanf("%d%d%d%d%",&x0,&y0,&x1,&y1); r=0; for (y=y0;y<=y1;y++) { for (x=x0;x<=x1;x++) { if (map[y*BYTES_PER_ROW+x/8]&(1<<(x%8))) { r++; break; } } } printf("%d\n",r); } } return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报