Volume0-0099 Surf Smelt Fishing Contest II

イベントが入力される都度、最大値を求めるという問題。以前解いたRMQと似ているなと思い、RMQと同じ平方分割で実装してみました。

１．各人のワカサギの量を入れる配列Aと、√n人のワカサギの最大値を入れるバケット配列Bを用意。
２．入力のたびにAの内容とBの内容を更新
３．最大値とその人の番号を、小さい方から探索

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define BMAX 1000

int max(int a,int b){
 if(a > b)return a;
 return b;
}

int min(int a,int b){
 if(a > b)return b;
 return a;
}

int main(){
 int n,q;
 int i,j,k;
 int an,vn,x;
 int maxi;
 int *A;
 int B[BMAX];
 int b,L,R;
 int idx;

 scanf("%d %d",&n,&q);
 b=floor(sqrt(n));
 A=(int *)malloc(sizeof(int) * 1000001);

 for(i=0;i<n;i++){
  A[i]=0;
 }
 for(i=0;i<BMAX;i++){
  B[i]=0;
 }

 for(i=0;i<q;i++){

  /*update*/
   scanf("%d %d",&an,&vn);
   x=an-1;
   A[x]+=vn;
   maxi=A[(x/b)*b];
   R=min((x/b+1)*b-1,n-1);
   for(j=(x/b)*b+1;j<=R;j++)maxi=max(maxi,A[j]);
   B[x/b]=maxi;

  /*find*/
   maxi=-1;
   for(j=0;j<=(n-1)/b;j++){
     if(B[j] > maxi){
       maxi=B[j];
       idx=j;
     }
    }

   for(k=b*idx;k<b*(idx+1);k++){
     if(A[k]==maxi){
       printf("%d %d\n",k+1,maxi);
       break;
     }
   }

 }

return 0;
}

今回、人の添え字は1始まりだったのですが、平方分割で考える場合、0始まりが良いので、-1して0始まりに直しました。
一番困ったのは配列のサイズです。nの最大値が1000000で、A[1000000]と宣言するとエラーが出てしまいました。
こういう時はメモリを動的に確保すると良いらしいです。

 A=(int *)malloc(sizeof(int) * 1000001);

知らなかった…過去にも同じことで困ってたので、非常にためになりました。

参考
9cguide.appspot.com

はなたの日記

ギターのコードについて書きます

Volume0-0099 Surf Smelt Fishing Contest II