佛山模板建站软件,网站一般费用,wordpress主题个人博客,wordpress wooyun1.借教室 思路
1.随着订单的增加#xff0c;每天可用的教室越来越少#xff0c;二分查找最后一个教室没有出现负数的订单编号 2.每个订单的操作是 [s, t] 全部减去 d
#includeiostream
#includecstring
using namespace std;
const int N 1e6 10;
int d[…1.借教室 思路
1.随着订单的增加每天可用的教室越来越少二分查找最后一个教室没有出现负数的订单编号 2.每个订单的操作是 [s, t] 全部减去 d
#includeiostream
#includecstring
using namespace std;
const int N 1e6 10;
int d[N], s[N], t[N], a[N];
long long b[N];
int n, m;int check(int mid){memset(b, 0, sizeof(b));for(int i 1; i mid; i){// 差分数组b[s[i]] d[i];b[t[i] 1] - d[i];}for(int i 1; i n; i){// 累加已经用过的教室即前缀和来判断教室是否足够b[i] b[i - 1];if(b[i] a[i]) return 0;}return 1;
}int main(){scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d, a[i]);for(int i 1; i m; i) scanf(%d%d%d, d[i], s[i], t[i]);int l 0, r m 1;while(l 1 r){int mid (l r) / 2;if(check(mid)) l mid;else r mid;}// 此时 r 为第一个不满足的编号if(r m 1) printf(0);else printf(-1\n%d, r);return 0;
}2.分巧克力 思路
二分巧克力边长注意长和宽都要除以 mid防止出现 1 * 100 除以 2 * 2的情况
#includeiostream
using namespace std;
const int N 1e5 10;
int h[N], w[N];
int n, k;int check(int mid){int sum 0;for(int i 1; i n; i){// 注意比如 1 * 100mid 为 2不可分sum (h[i] / mid) * (w[i] / mid);}if(sum k) return 1;else return 0;
}int main(){scanf(%d%d, n, k);for(int i 1; i n; i) scanf(%d%d, h[i], w[i]);int l 0, r 1e5 1;while(l 1 r){int mid (l r) / 2;if(check(mid)) l mid;else r mid;}printf(%d, l);return 0;
}3.管道 思路
1.二分最早打开的时间 2.合并已经打开的区间
#includeiostream
#includealgorithm
using namespace std;
const int N 1e5 10;
pairint, int q[N]; // 存储左右端点
int L[N], S[N];
int n, len;int check(int mid){int cnt 0;for(int i 0; i n; i){if(mid S[i]){// 延伸出去的距离int t mid - S[i];int l max(1, L[i] - t), r min(1ll * len, 1ll * L[i] t);q[cnt] make_pair(l, r);}}//区间合并sort(q, q cnt);int st -1, ed -1;for(int i 0; i cnt; i){if(ed 1 q[i].first) ed max(ed, q[i].second);else st q[i].first, ed q[i].second;}return st 1 ed len;
}int main(){scanf(%d%d, n, len);for(int i 0; i n; i) scanf(%d%d, L[i], S[i]);int l 0, r 2e9 1;while(l 1 r){int mid (1ll * l r) / 2;if(check(mid)) r mid;else l mid;}printf(%d, r);return 0;
}4.技能升级 思路
1.多路归并把所有等差数列放在一个数组从大到小排序选前 m 个数 2.大于等于 x 的个数一定大于等于 m 个二分 xx 为从大到小排名为 m 的数 3.每个数列大于等于 x 的个数为 (a - x) / b 1 4.每个数列大于等于 x 的总和为 (首项 末项) * 项数 / 2
#includeiostream
using namespace std;
const int N 1e5 10;
int a[N], b[N];
int n, m;// 判断大于等于 mid 的个数是否大于等于 m
int check(int mid){long long cnt 0;for(int i 0; i n; i){if(a[i] mid) cnt (a[i] - mid) / b[i] 1;}return cnt m;
}int main(){scanf(%d%d, n, m);for(int i 0; i n; i) scanf(%d%d, a[i], b[i]);int l 0, r 1e6 1;while(l 1 r){int mid (l r) / 2;if(check(mid)) l mid;else r mid;}long long sum 0, cnt 0;for(int i 0; i n; i){if(a[i] l){// 计算项数int c (a[i] - r) / b[i] 1;// 计算末项int ed a[i] - b[i] * (c - 1);// 等差数列求和sum 1ll * (a[i] ed) * c / 2; // 计算有多少项可能有多余cnt c;}}// 减去多余的项printf(%lld, sum - (cnt - m) * l);return 0;
}5.冶炼金属 思路
方法1二分左右边界 方法2推导公式a / x ba / x (b 1);
// 方法1
#includeiostream
using namespace std;
const int N 1e4 10;
int a[N], b[N];
int n;// 找到最大值
int check1(int mid){for(int i 0; i n; i){if(a[i] / mid b[i]) return 0;}return 1;
}// 找到最小值
int check2(int mid){for(int i 0; i n; i){if(a[i] / mid b[i]) return 0;}return 1;
}int main(){scanf(%d, n);for(int i 0; i n; i) scanf(%d%d, a[i], b[i]);int l 0, r 1e9 1;while(l 1 r){int mid (l r) / 2;if(check1(mid)) l mid;else r mid;}int res1 l;l 0, r 1e9 1;while(l 1 r){int mid (l r) / 2;if(check2(mid)) r mid;else l mid;}int res2 r;printf(%d %d, res2, res1);return 0;
}// 方法2
#includeiostream
using namespace std;
const int N 1e4 10;
int a, b;
int n;int main(){scanf(%d, n);int res1 1, res2 1e9;for(int i 0; i n; i){scanf(%d%d, a, b);res1 max(res1, a / (b 1) 1);res2 min(res2, a / b);}printf(%d %d, res1, res2);return 0;
}6.数的范围 思路
二分左右边界
#includeiostream
using namespace std;
const int N 1e5 10;
int a[N];
int n, q;// 找最小值
int check1(int mid, int k){return a[mid] k;
}// 找最大值
int check2(int mid, int k){return a[mid] k;
}int main(){scanf(%d%d, n, q);for(int i 0; i n; i) scanf(%d, a[i]);int k;while(q--){scanf(%d, k);int l -1, r n;while(l 1 r){int mid (l r) / 2;if(check1(mid, k)) l mid;else r mid;}int res1 r;l 0, r n;while(l 1 r){int mid (l r) / 2;if(check2(mid, k)) l mid;else r mid;}int res2 l;if(a[res1] k a[res2] k) printf(%d %d\n, res1, res2);else printf(-1 -1\n);}return 0;
}7.最佳牛围栏 思路
1.二分平均值每个数先减去平均值转化成是否存在长度大于等于 f 的非零子段和 2.舍去很小的前缀和保留大的前缀和
#includeiostream
using namespace std;
const int N 1e5 10;
double a[N], s[N];
int n, f;int check(double mid){double res 1e9, ans -1e9;for(int i f; i n; i){// 可以舍去的前缀和res min(res, s[i - f]);// 保留的前缀和ans max(ans, s[i] - res);}return ans 0;
}int main(){scanf(%d%d, n, f);for(int i 1; i n; i){scanf(%lf, a[i]);}double l 0, r 2001;while(l 1e-5 r){double mid (l r) / 2;for(int i 1; i n; i){s[i] s[i - 1] a[i] - mid;}if(check(mid)) l mid;else r mid;}// l 1e-5 rint ans r * 1000;printf(%d, ans);return 0;
}
