nowcoder 牛客挑战赛61 D

發表於 更新於 分類於 Disqus： 文章字數： 434 所需閱讀時間 ≈ 1 分鐘

D https://ac.nowcoder.com/acm/contest/11201/D

总思路没问题, dijkstra不能带log, 2s时间卡时限了

没有log的也800ms, 稍微一个3倍都过不了

所以需要的是点的值要么是初始的要么是推导(当前最大值-定值k)生成的, 双队列+指针实现

没过这题也能+3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
#define pb push_back
#define c(a,b) ((a)*(m)+(b))

int read(){int r; scanf("%d", &r);return r;} // read

int a[500010];
int n,m,k;

bool vis[500010];

const int di[] = {-1,1,0,0,-1,1};
const int dj[] = {0,0,-1,1,1,-1};

vector< array<int,3> > startvij;

ll cost(int diff){
  fill(vis,vis + n*m,false);
  vector< array<int,3> > vp = {}; // 优先队列等含有log的会TLE
  ll sk = 0 ;
  vp = {};
  int i0 = 0;
  int i1 = 0;
  while(i0 < startvij.size() || i1 < vp.size()){
    int v = 0;
    int i = -1;
    int j = -1;
    if(i0 < startvij.size() && i1 < vp.size()){
      if(startvij[i0][0] >= vp[i1][0]){
        v = startvij[i0][0];
        i = startvij[i0][1];
        j = startvij[i0][2];
        i0++;
      }else{
        v = vp[i1][0];
        i = vp[i1][1];
        j = vp[i1][2];
        i1++;
      }
    }else if(i0 < startvij.size()){
      v = startvij[i0][0];
      i = startvij[i0][1];
      j = startvij[i0][2];
      i0++;
    }else {
      v = vp[i1][0];
      i = vp[i1][1];
      j = vp[i1][2];
      i1++;
    }
    if(vis[c(i,j)])continue;
    vis[c(i,j)] = true;
    sk += v - a[c(i,j)];
    rep(w,0,6){
      int ni = i + di[w];
      int nj = j + dj[w];
      if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
      if(a[c(ni,nj)] == -1) continue;
      if(vis[c(ni,nj)]) continue;
      if(v - diff > a[c(ni,nj)]){
        vp.pb({v - diff,ni,nj});
      }
    }
  }
  return sk;
}

int main(){
  n = read();
  m = read();
  k = read();

  rep(i,0,n){
    rep(j,0,m){
      a[c(i,j)] = read();
      if(a[c(i,j)] != -1) startvij.pb({a[c(i,j)],i,j});
    }
  }
  sort(startvij.begin(), startvij.end(), greater<array<int,3>>());

  int l = 0;
  int r = 1000;
  int ans = 1000;
  while(l <= r){
    int mid = (l+r)/2;
    if(cost(mid) <= k){
      ans = mid;
      r = mid - 1;
    }else{
      l = mid + 1;
    }
  }
  cout<<ans<<endl;
  return 0;
}