p1928.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 2510;
struct point{ int k,x,y; };
point a[MAXN];
bool cmp(point a,point b){ return a.k > b.k; };
int main(){
    int N;
    cin >> N;
    while(N--){
        int r,c,k,n(0);
        cin >> r >> c >> k;
        for(int i = 1;i <= r;++i)
            for(int j = 1;j <= c;++j){
                int x;
                scanf("%d",&x);
                if(x){
                    a[n].k = x;
                    a[n].x = j;
                    a[n].y = i;
                    ++n;
                }
            }
        sort(a,a+n,cmp);
        int dis[MAXN],sum[MAXN];
        dis[0] = a[0].y + 1;
        sum[0] = a[0].k;
        for(int i = 1;i < n;++i){
            dis[i] = dis[i-1] + abs(a[i-1].x - a[i].x) + abs(a[i-1].y - a[i].y) + 1;
            sum[i] = sum[i-1] + a[i].k;
        }
        int s(0),t(n-1),m,ans(0);
        while(s <= t){
            m = s+t >> 1;
            if(dis[m] + a[m].y <= k){
                ans = sum[m];
                s = m + 1;
            }
            else t = m - 1;
        }
        cout << ans << endl;
    }
}