当前位置：网站首页>Discrimination of the interval of dichotomy question brushing record (Luogu question sheet)
Discrimination of the interval of dichotomy question brushing record (Luogu question sheet)
2022-07-02 12:10:00 【Tooth decay music】
Premise ：
Dichotomous condition ：
1、 There is scope
2、 Section
3、 Can judge whether a certain point meets the conditions , And can narrow the boundary
4、 monotonous
The board
Please pay attention to the value
Example ： 【 Deep base 13. example 1】 lookup
The maximum is the smallest
while(l < r){
ll mid = (l + r + 1) >> 1;
if(a[mid] < t)
l = mid;
else
r = mid - 1;
}
The minimum is the maximum
while(l <= r){
ll mid = (l + r) >> 1;
if(a[mid] < t)
l = mid + 1;
else
r = mid - 1;
}
A-B Number pair
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
ll a[maxn];
map<ll, ll> num;
int main(){
ll n, m;
scanf("%lld %lld",&n, &m);
int cnt = 0;
for (int i = 1; i <= n; ++i){
ll t;
scanf("%lld", &t);
if(!num[t])
a[++cnt] = t;
++num[t];
}
sort(a + 1, a + cnt + 1);
ll ans = 0;
for (int i = 1; i <= cnt; ++i){
ll l = 1, r = cnt;
ll goal = a[i] + m;
while(l < r){
ll mid = (l + r) >> 1;
if(a[mid] < goal)
l = mid + 1;
else
r = mid;
}
if(a[l] != goal) continue;
ans += 1ll * num[a[i]] * num[a[l]];
}
cout << ans << endl;
return 0;
}
P1024 [NOIP2001 Improvement group ] Solve the cubic equation of one variable
I even thought wrong
The first answer given is decimal , So we can infer that the answer is [-1, 1] in , instead of [-100,100], Traverse the interval and then divide
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1e6 + 5;
double a, b, c, d;
inline double ge(double i){
return a * i * i * i + b * i * i + c * i + d;
}
int main(){
cin >> a >> b >> c >> d;
int cnt = 0;
for (int i = -100; i <= 100; ++i){
double templ = ge(i*1.0);
double tempr = ge(i + 1.0);
if(templ == 0) {
printf("%.2f ", (double)i);
++cnt;
continue;
}
if(templ * tempr < 0){
double l = i, r = i + 1.0;
while(r - l >= 1e-3){
double mid = (l + r) / 2.0;
if(ge(l) * ge(mid) <= 0){
r = mid;
}
else
l = mid;
}
printf("%.2f ", l);
++cnt;
}
if(cnt >= 3)
break;
}
return 0;
}
P1678 Worry about the college entrance examination
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
const int maxn = 1e6 + 5;
#define ll long long
ll n, m;
ll a[maxn], b[maxn];
int main(){
fill(b, b + maxn, LLONG_MAX);
cin >> m >> n;
for (int i = 1; i <= m; ++i){
cin >> b[i];
}
for (int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(b + 1, b + m + 1);
ll ans = 0;
for (int i = 1; i <= n; ++i){
ll l = 1, r = m;
while(l <= r){
ll mid = (l + r) >> 1;
if(b[mid] < a[i])
l = mid + 1;
else
r = mid - 1;
}
ans += min(abs(b[l - 1] - a[i]),min(abs(b[l] - a[i]), abs(b[l + 1] - a[i])));
}
cout << ans;
return 0;
}
P1163 A bank loan
There's a formula , You can also use multiplication , The complexity is the same as dichotomy 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
const int maxn = 1e6 + 5;
#define ll long long
double a, b, c;
double gett(double mid){
double temp = 0;
double te = (1.0 + mid);
for (int i = 0; i < c; ++i){
temp += 1.0 * b / te;
te *= (1.0 + mid);
}
return temp;
}
int main(){
cin >> a >> b >> c;
double l = 0, r = a;
while(r - l >= 0.0001){
double mid = (l + r) / 2.0;
double temp = gett(mid);
if(temp >= a){
l = mid;
}
else if(temp < a)
r = mid;
}
l = l * 100.0;
printf("%.1f", l);
return 0;
}
P1873 [COCI 2011/2012 #5] EKO / Cut down trees
done , Once at that time , Now? wa One hair
This question is the smallest of the largest , So use the （l <= r）,(l < r) Meeting wa
ll n, m;
ll a[maxn], pre[maxn];
bool check(ll mid){
ll sum = 0;
for (int i = 1; i <= n; ++i){
if(a[i] - mid > 0)
sum += (a[i] - mid);
}
if(sum >= m) return true;
return false;
}
int main() {
IOS;
cin >> n >> m;
ll r = -1, l = INT_MAX;
for(int i = 1; i <= n; ++i){
cin >> a[i];
r = max(r, a[i]);
l = min(l, a[i]);
}
while (l <= r){
ll mid = (l + r) / 2;
if (check(mid))
l = mid + 1;
else
r = mid - 1;
}
cout << r;
return 0;
}
P2440 Wood processing
Maximum and minimum
ll n, m;
ll a[maxn];
bool check(ll mid){
ll sum = 0;
for (int i = 1; i <= n; ++i){
sum += a[i] / mid;
}
if(sum >= m) return true;
return false;
}
int main() {
IOS;
// freopen("P1908_6.in","r",stdin);// Read in the data
// freopen("P1908.out","w",stdout); // Output data
cin >> n >> m;
ll r = -1, l = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
r = max(r, a[i]);
}
while (l <= r){
ll mid = (l + r) / 2;
if(mid == 0){
r = 0;
break;
}
if (check(mid))
l = mid + 1;
else
r = mid - 1;
}
cout << r;
return 0;
}
P2678 [NOIP2015 Improvement group ] Rock jumping
The minimum is the maximum , The length of two points , Not stones , Judge whether the stone is used or not , Record whether the number of moving blocks exceeds the given number of questions
ll n, m, L;
ll a[maxn];
bool check(ll mid){
ll sum = 0, cnt = 0;
ll pre = 0;
bool flag = true;
for (int i = 1; i <= n; ++i){
if(a[i] - pre < mid){
++cnt;
flag = false;
}
if(!flag){
flag = true;
}
else {
pre = a[i];
}
if(cnt > m)
return false;
}
if(L - pre < mid)
++cnt;
if(cnt <= m) return true;
return false;
}
int main() {
IOS;
// freopen("P1908_6.in","r",stdin);// Read in the data
// freopen("P1908.out","w",stdout); // Output data
cin >> L >> n >> m;
ll l = 0, r = LLONG_MAX;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(a + 1, a + n + 1);
ll ans = 0;
while(l <= r){
ll mid = (l + r) / 2;
if(check(mid)){
//ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
//cout << ans;
cout << r;
return 0;
}
P1182 Sequence segmentation Section II
ll n, m;
ll a[maxn];
bool check(ll mid){
ll cnt = 1, temp = 0;
for (int i = 1; i <= n; ++i){
if(temp + a[i] <= mid)
temp += a[i];
else {
temp = a[i];
++cnt;
}
}
if(cnt > m)
return true;
return false;
}
int main() {
IOS;
// freopen("P1908_6.in","r",stdin);// Read in the data
// freopen("P1908.out","w",stdout); // Output data
cin >> n >> m;
ll l = 0, r = 0;
for (int i = 1; i <= n; ++i){
cin >> a[i];
r += a[i];
l = max(l, a[i]);
}
while(l < r){
ll mid = (l + r) / 2;
if(check(mid)) {
l = mid + 1;
}
else
r = mid;
}
cout << l;
return 0;
}
P3853 [TJOI2007] Road sign setting
wa Crazy , because Just divide and subtract one
ll n, m, L, k;
ll a[maxn];
bool check(ll mid){
ll cnt = 0;
for (int i = 2; i <= n; ++i){
cnt += (a[i] - a[i - 1]) / mid + ((a[i] - a[i - 1]) % mid == 0 ? -1 : 0);
}
if(cnt > k)
return true;
return false;
}
int main() {
IOS;
// freopen("P1908_6.in","r",stdin);// Read in the data
// freopen("P1908.out","w",stdout); // Output data
cin >> L >> n >> k;
a[0] = 0;
ll l = 1, r = 0;
for (int i = 1; i <= n; ++i){
cin >> a[i];
if(i > 1)
r = max(r, a[i] - a[i - 1]);
}
while (l < r){
ll mid = (l + r) / 2;
if (check(mid)){
l = mid + 1;
}
else
r = mid;
}
cout << l;
return 0;
}
P3743 kotori The equipment
It is necessary to understand the relationship between equipment energy and charging capacity
ll n, m, L, k;
pair<ll, ll> a[maxn];
bool check(double mid){
double sum = 0, temp = mid * k;
for (int i = 1; i <= n; ++i){
if(mid * a[i].first > a[i].second)
sum += 1.0 * (mid * a[i].first - a[i].second);
}
return temp >= sum;
}
int main() {
IOS;
// freopen("P1908_6.in","r",stdin);// Read in the data
// freopen("P1908.out","w",stdout); // Output data
cin >> n >> k;
double l = 0, r = 1e10 + 5.0;
ll sum = 0;
for (int i = 1; i <= n; ++i){
cin >> a[i].first >> a[i].second;
sum+=a[i].first;
}
if(sum <= k) {
cout << -1;
return 0;
}
// How long can it be used
while (r - l >= 0.00001){
double mid = (l + r) / 2;
if (check(mid)){
l = mid;
}
else
r = mid;
}
cout << l;
return 0;
}
Recommended blog
边栏推荐
- GGHIGHLIGHT: EASY WAY TO HIGHLIGHT A GGPLOT IN R
- 刷题---二叉树--2
- 基于Arduino和ESP8266的Blink代码运行成功（包含错误分析）
- XSS labs master shooting range environment construction and 1-6 problem solving ideas
- (C language) octal conversion decimal
- The most understandable f-string tutorial in history, collecting this one is enough
- Depth filter of SvO2 series
- Gaode map test case
- Leetcode739 每日温度
- ORB-SLAM2不同线程间的数据共享与传递
猜你喜欢
WSL 2 will not be installed yet? It's enough to read this article
小程序链接生成
Map and set
Jenkins voucher management
深入理解PyTorch中的nn.Embedding
Seriation in R: How to Optimally Order Objects in a Data Matrice
YYGH-BUG-04
xss-labs-master靶场环境搭建与1-6关解题思路
From scratch, develop a web office suite (3): mouse events
YYGH-BUG-04
随机推荐
Leetcode922 按奇偶排序数组 II
How does Premiere (PR) import the preset mogrt template?
堆（優先級隊列）
字符串回文hash 模板题 O(1)判字符串是否回文
Repeat, tile and repeat in pytorch_ The difference between interleave
Leetcode14 longest public prefix
Brush questions --- binary tree --2
Time format display
自然语言处理系列（三）——LSTM
Applet link generation
Natural language processing series (III) -- LSTM
SVO2系列之深度滤波DepthFilter
二分刷题记录（洛谷题单）区间的甄别
Map and set
Gaode map test case
Leetcode122 the best time to buy and sell stocks II
Find the factorial of a positive integer within 16, that is, the class of n (0= < n < =16). Enter 1111 to exit.
GGPlot Examples Best Reference
Leetcode209 长度最小的子数组
倍增 LCA（最近公共祖先）