8.17日二分测试总结
分数情况
| A.砍树 | B.买木头 | C.数列分段2 | D.吃冰棍 | E.跳石头 | F.奶牛晒衣服 |
|---|---|---|---|---|---|
| 100 | 80 | 100 | \(_{没做:(}\) | 10 | 0 |
总体分数
\(_{很惨}\)
T1. P1873 [COCI 2011/2012 #5] EKO / 砍树
题目传送门
问题分析
运用二分答案与
check函数
check函数用来检测答案是否合法
\(AC\) \(Code:\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 7;
int n, m;
int a[maxn];
bool check(int x)
{
int ans = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i] > x)
{
ans += (a[i] - x);
}
}
return ans >= m;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int maxx = 0;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
maxx = max(maxx, a[i]);
}
int l = 1, r = maxx + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (check(mid))
{
l = mid;
}
else
{
r = mid;
}
}
cout << l << "\n";
return 0;
}
T2. B3880 [信息与未来 2015] 买木头
题目传送门
\(Wrong\) \(Code:\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int a[maxn], b[maxn];
int n, m;
bool check(int x)
{
int sum = 0;
for (int i = 1; i <= n; ++i)
{
sum += a[i] / x * b[i];
if (sum >= m)
{
return 1;
}
}
return 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> a[1] >> b[1];
int maxx = INT_MIN;
for (int i = 2; i <= m; ++i)
{
a[i] = ((a[i - 1] * 37011 + 10193) % 10000) + 1;
b[i] = ((b[i - 1] * 73011 + 24793) % 100) + 1;
maxx = max(a[i], maxx);
}
int l = 0, r = maxx + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (check(mid))
{
l = mid;
}
else
{
r = mid;
}
}
cout << l << "\n";
return 0;
}
/*
10 10000 8 20
*/
问题分析
通过题目给的两个公式：
- \(l_i=((l_{i-1}\times37011+10193) \bmod 10000)+1\)
- \(s_i=((s_{i-1}\times73011+24793) \bmod 100)+1\)
和给出的初始值求出后面的每个数的大小
通过二分答案与
check函数查找合法的答案
错误分析
- 细节决定成败
题目中说：
一行四个整数 \(n,m,l_1,s_1\)。其中 \(l_1\) 是第一个供货商木头的长度，\(s_1\) 是第一个供货商木头的数量。
而我的输入为什么是 \(m\) ！！！ \(_{气死我了}\)
\(AC\) \(Code:\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int a[maxn], b[maxn];
int n, m;
bool check(int x)
{
int sum = 0;
for (int i = 1; i <= n; ++i)
{
sum += a[i] / x * b[i];
if (sum >= m)
{
return 1;
}
}
return 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> a[1] >> b[1];
int maxx = INT_MIN;
for (int i = 2; i <= n; ++i)
{
a[i] = ((a[i - 1] * 37011 + 10193) % 10000) + 1;
b[i] = ((b[i - 1] * 73011 + 24793) % 100) + 1;
maxx = max(a[i], maxx);
}
int l = 0, r = maxx + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (check(mid))
{
l = mid;
}
else
{
r = mid;
}
}
cout << l << "\n";
return 0;
}
/*
10 10000 8 20
*/
T3. P1182 数列分段 Section II
题目传送门
前置题目 P1181 数列分段 Section I
\(AC\) \(Code:\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int a[maxn];
int n, m;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int sum = 0, ans = 1;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
if (sum + a[i] <= m)
{
sum += a[i];
}
else
{
ans++;
sum = a[i];
}
}
cout << ans << "\n";
return 0;
}
回到正题(P1182)
使用P1181的大部分代码作为P1182的
check函数
具体代码如下
\(AC\) \(Code:\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
int n, m;
int a[maxn];
bool check(int x)
{
int cnt = 1;
int sum = 0;
for (int i = 1; i <= n; ++i)
{
if (sum + a[i] <= x)
{
sum += a[i];
}
else
{
cnt++;
sum = a[i];
}
}
return cnt <= m;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int num = 0;
int maxx = 0;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
maxx = max(maxx, a[i]);
num += a[i];
}
int l = maxx - 1;
int r = num + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (check(mid))
{
r = mid;
}
else
{
l = mid;
}
}
cout << r << "\n";
return 0;
}
/*
5 3
4 2 4 5 1
*/
T4. B3629 吃冰棍
题目传送门
\(Wrong\) \(Code:\)
问题分析
做的时候想的是用模拟 \(+\) 枚举
题目说是二分
但是二分没有想到怎么做
标签：二分,cout,int,mid,long,maxn,测试,8.17,check From： https://www.cnblogs.com/yucheng0630/p/18365442