9.15 滴滴笔试

T1（二分）

#include <bits/stdc++.h>#define endl '\n'using namespace std;typedef long long LL;const int N = 1e5 + 10;int n, k;
int a[N];bool check(int mid) {int rec = 1e9, cnt = 1;for(int i = 0; i < n; i ++) {int j = i;while(j < n && a[j] - a[i] < mid) j ++ ;if(j < n) rec = min(rec, a[j] - a[i]), cnt ++;i = j - 1;}return cnt >= k && rec >= mid;
}void solve() {cin >> n >> k;for(int i = 0; i < n; i ++) cin >> a[i];int l = 1, r = 1e6 + 10;while(l < r) {int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}cout << r << endl;
}int main() {cin.tie(0); cout.tie(0);std::ios::sync_with_stdio(false);int T = 1;
//	cin >> T;while(T --) {solve();}return 0;
}

T2（01BFS）

#include <bits/stdc++.h>#define x first
#define y second#define endl '\n'using namespace std;typedef long long LL;
typedef pair<int, int> PII;const int N = 1e5 + 10;int n, m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};void solve() {cin >> n >> m;vector<vector<int>> g(n, vector<int> (m));vector<vector<int>> dist(n, vector<int> (m, 1e9));for(int i = 0; i < n; i ++) {for(int j = 0; j < m; j ++) {cin >> g[i][j];}}deque<PII> q;q.push_back({0, 0});dist[0][0] = g[0][0];while(q.size()) {auto t = q.front(); q.pop_front();int x = t.x, y = t.y;for(int i = 0; i < 4; i ++) {int a = x + dx[i], b = y + dy[i];if(a >= 0 && a < n && b >= 0 && b < m) {if(dist[a][b] > dist[x][y] + g[a][b]) {dist[a][b] = dist[x][y] + g[a][b];if(g[a][b] == 1) {q.push_back({a, b});} else {q.push_front({a, b});}}}}}cout << dist[n - 1][m - 1] << endl;
}int main() {cin.tie(0); cout.tie(0);std::ios::sync_with_stdio(false);int T = 1;
//	cin >> T;while(T --) {solve();}return 0;
}