zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1242-网线主管（C++代码）二分
浏览：1468

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

信息学奥赛一本通T1242-网线主管（C++代码）二分

　　作者: zjh　　　　发表时间：2019-12-29 17:34:49 浏览：1468　|　评论：0　

原题链接：信息学奥赛一本通T1242-网线主管

思路：
	1. 	我们可以列举所有网线可能的长度len（0，max] ，(max即输入数据中最大的), 计算出每种长度下网线的数量
	2. 	时间复杂度为 O(max*n)，100km的长度 * n，必然超时，所以我们在列举网线长度时，可以选择二分算法
	3. 	假如当前在len区间中选择了中间一个数mid，算出的网线数量cnt < k, 那么就说明答案在以mid为分界的左区间（不包括mid），反之则在以mid为分界的右区间（包括mid）
	4. 	需要注意的是精度的处理，如果是小数二分的话那就比较麻烦了，所以我们在输入数据的时候*100，让其变成整数，输出答案时/100即可

```cpp
#include "cstdio"
#include "cstdlib"
#include "iostream"
#include "sstream"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "map"
#include "vector"
#include "stack"
#include "set"
#include "climits"

using namespace std;

typedef long long ll;
typedef unsigned long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int INF = INT_MAX;
const int mod = 1e9 + 7;

inline ll read() {
    char c = getchar();
    ll x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

int n, k;
vector<int> A;

int main() {
    cin >> n >> k;
    double ai;
    int l = 0, r = 0;
	// 输入，*100转整型，求max
    for (int i = 0; i < n; ++i) cin >> ai, A.push_back(ai * 100), r = max(r, A[i]);
	// 二分
    while (l < r) {
		// +1防止死循环, 对答案没有影响
        int mid = (l + r + 1) >> 1, cnt = 0;
        for (int i = 0; i < n; ++i) cnt += A[i] / mid;
        if (cnt >= k) l = mid;	// 对于当前mid，如果有解，即确定在右区间(包括mid)
        else r = mid - 1; // 相反则在左区间
    }
    printf("%.2lf\n", (l >= 1 ? l / 100.0 : 0));
    return 0;
}

```

0.0分

68 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zjh

TA的其他文章

你可能喜欢

1010111010101010：母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

信息学奥赛一本通T1242-网线主管（C++代码）二分

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

母牛的故事（C语言代码）

采药（C语言代码）

zjh

TA的其他文章

你可能喜欢

1010111010101010：母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

信息学奥赛一本通T1242-网线主管 （C++代码）二分

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

母牛的故事 （C语言代码）

采药 （C语言代码）

1010111010101010：母牛的故事（C语言代码）

信息学奥赛一本通T1242-网线主管（C++代码）二分

　　评论区

大神老白（C语言代码）

母牛的故事（C语言代码）

采药（C语言代码）