Biathlon Track

Codeforces Round #242 (Div. 2) D:http://codeforces.com/contest/424/problem/D

题意：给你一个n*m的矩阵，每个格子上面有个数字，在相邻格子之间会有一定的费用，费用根据相邻格子的大小关系确定。让你费用最接近一个数的矩阵。

题解：一看题目，想了一下，预处理，然后猜到要用二分。但是二维的怎么二分，一直没有想到什么办法，一直想的是(n*mlog(n*m))的算法，所以不对了。其实应该固定一个起点，作为矩阵的左上角的点，然后枚举右下角的纵坐标，对于右下角的横坐标就可以二分寻找了。但是这里是找最接近的数，一开始以为二分找不到，现在才知道二分的最后可以找到的就是最接近的那个数，同时二分的写法也要注意，不能写成a[mid]<=number，这样会陷入死循环。还有，这一题要预处理出一些点的距离。其实，这一题还可以直接打暴力，四层for也是能过的。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int N=;

 int a[N][N];

 int l[N][N],r[N][N],u[N][N],d[N][N];

 int n,m,t;

 int tp,tu,td;

 void solve(){

    memset(l,,sizeof(l));

    memset(r,,sizeof(r));

    memset(u,,sizeof(u));

    memset(d,,sizeof(d));

    for(int i=;i<=n;i++){

     for(int j=;j<=m;j++){

         l[i][j]=l[i][j-];

         if(j==)continue;

         if(a[i][j]>a[i][j-])

             l[i][j]+=tu;

         else if(a[i][j]==a[i][j-])

             l[i][j]+=tp;

         else

             l[i][j]+=td;

      }

    }

    for(int i=;i<=n;i++){

     for(int j=m;j>=;j--){

         r[i][j]=r[i][j+];

         if(j==m)continue;

         if(a[i][j]>a[i][j+])

             r[i][j]+=tu;

         else if(a[i][j]==a[i][j+])

             r[i][j]+=tp;

         else

             r[i][j]+=td;

      }

    }

    for(int j=;j<=m;j++){

     for(int i=;i<=n;i++){

         u[i][j]=u[i-][j];

         if(i==)continue;

         if(a[i][j]>a[i-][j])

           u[i][j]+=tu;

         else if(a[i][j]==a[i-][j])

             u[i][j]+=tp;

         else

             u[i][j]+=td;

     }

    }

    for(int j=;j<=m;j++){

     for(int i=n;i>=;i--){

         d[i][j]=d[i+][j];

         if(i==n)continue;

         if(a[i][j]>a[i+][j])

           d[i][j]+=tu;

         else if(a[i][j]==a[i+][j])

             d[i][j]+=tp;

         else

             d[i][j]+=td;

     }

    }

 }

 int getsum(int l1,int r1,int l2,int r2){

     return l[l1][r2]-l[l1][r1]+u[l2][r2]-u[l1][r2]+r[l2][r1]-r[l2][r2]+d[l1][r1]-d[l2][r1];

 }

 int ans,x1,x2,y1,y2;

 int main(){

   scanf("%d%d%d",&n,&m,&t);

   scanf("%d%d%d",&tp,&tu,&td);

   for(int i=;i<=n;i++)

     for(int j=;j<=m;j++)

      cin>>a[i][j];

       solve();

       ans=2e9;

     for(int i=;i<=n;i++){

         for(int j=;j<=m;j++){

             for(int  k=j+;k<=m;k++){

                int l=i+,r=n;

                if(l>r)continue;

                while(l<r){

                 int mid=(l+r)/;

                 int temp=getsum(i,j,mid,k);

                 if(temp>=t){

                     r=mid;

                 }

                 else

                     l=mid+;

                }

               int ts=getsum(i,j,l,k);

               if(abs(ts-t)<abs(ans-t)){

                  ans=ts;

                  x1=i;y1=j;

                  x2=l;y2=k;

               }

               if(l<n){

                 ts=getsum(i,j,l+,k);

               if(abs(ts-t)<abs(ans-t)){

                  ans=ts;

                  x1=i;y1=j;

                  x2=l+;y2=k;

               }

             }

               if(l>i+){

                 ts=getsum(i,j,l-,k);

               if(abs(ts-t)<abs(ans-t)){

                  ans=ts;

                  x1=i;y1=j;

                  x2=l-;y2=k;

               }

             }

         }

     }

   }

   printf("%d %d %d %d\n",x1,y1,x2,y2);

 }

巴特西

Biathlon Track

最新文章

热门文章