蓝桥杯刷题（也就写写水题骗骗自己了）

目录二分答案P1873 [COCI 2011/2012 #5] EKO / 砍树P2678 [NOIP 2015 提高组] 跳石头P8647 [蓝桥杯 2017 省 AB] 分巧克力贪心P1803 凌乱的yyy / 线段覆盖P1090 [NOIP 2004 提高组] 合并果子记忆化搜索P1434 [SHOI2002] 滑雪二分答案P1873 [COCI 2011/2012 #5] EKO / 砍树#include bits/stdc.h using namespace std; #define int long long int n, m; bool check(int mid, vectorint high) { int sum 0; for (int num : high) sum max(num - mid, (int)0); return sum m; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; vectorint high(n); int right 0; for (int i 0; i n; i) { cin high[i]; right max(right, high[i]); } int left 0; while (left 1 right) { int mid left - (left - right) / 2; if (check(mid, high)) left mid; else right mid; } cout left; return 0; }P2678 [NOIP 2015 提高组] 跳石头#include bits/stdc.h using namespace std; #define int long long int L, N, M; bool check(int mid, vectorint dis) { int cnt 0; int current 0; for (int i 0; i N; i) { if (dis[i] - current mid) cnt; else current dis[i]; } if (L - current mid) cnt; return cnt M; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin L N M; if (N 0) { cout L; return 0; } vectorint dis(N); for (int i 0; i N; i) cin dis[i]; int left 0; int right L; while (left 1 right) { int mid left - (left - right) / 2; if (check(mid, dis)) left mid; else right mid; } cout left; return 0; }P8647 [蓝桥杯 2017 省 AB] 分巧克力#include bits/stdc.h using namespace std; int n, k; bool check(int len, vectorvectorint gra) { int cnt 0; for (int i 0; i n; i) { cnt (gra[i][0] / len) * (gra[i][1] / len); } return cnt k; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k; vectorvectorint gra(n, vectorint(2)); for (int i 0; i n; i) cin gra[i][0] gra[i][1]; int left 0; int right 1e5; while (left 1 right) { int mid left - (left - right) / 2; if (check(mid, gra)) left mid; else right mid; } cout left; return 0; }贪心P1803 凌乱的yyy / 线段覆盖#include bits/stdc.h using namespace std; int n; int ans; bool com(const pairint, int a, const pairint, int b) { return a.second b.second; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; vectorpairint, int time(n); for (int i 0; i n; i) cin time[i].first time[i].second; sort(time.begin(), time.end(), com); int cur 0; for (int i 0; i n; i) { if (time[i].first cur) { ans; cur time[i].second; } } cout ans; return 0; }P1090 [NOIP 2004 提高组] 合并果子哈夫曼数、小根堆#include bits/stdc.h using namespace std; #define int long long int n; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; priority_queueint, vectorint, greaterint q; int t; for (int i 0; i n; i) { cin t; q.push(t); } int ans 0; while (q.size() 1) { int a q.top(); q.pop(); a q.top(); q.pop(); ans a; q.push(a); } cout ans; return 0; }如果忘记小根堆怎么构造可以构造大根堆每个数*-1存进去相当于小根堆#include bits/stdc.h using namespace std; #define int long long int n; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; priority_queueint q; // 大根堆 int t; for (int i 0; i n; i) { cin t; t * -1; q.push(t); } int ans 0; while (q.size() 1) { int a q.top(); q.pop(); a q.top(); q.pop(); ans a * (-1); q.push(a); } cout ans; return 0; }记忆化搜索P1434 [SHOI2002] 滑雪#include bits/stdc.h using namespace std; int dx[] {0, 1, 0, -1}; int dy[] {-1, 0, 1, 0}; int r, c; vectorvectorint gra; vectorvectorint dis; int ans; int dfs(int x, int y) { if (dis[x][y]) return dis[x][y]; int len 1; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || ny 0 || nx r || ny c) continue; if (gra[nx][ny] gra[x][y]) continue; len max(len, dfs(nx, ny) 1); } dis[x][y] len; return len; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin r c; gra.resize(r, vectorint(c)); dis.resize(r, vectorint(c)); for (int i 0; i r; i) for (int j 0; j c; j) cin gra[i][j]; for (int i 0; i r; i) for (int j 0; j c; j) ans max(ans, dfs(i, j)); cout ans; return 0; }