2021-07-06 POJ1064

本文主要是介绍2021-07-06 POJ1064，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目

仙境的居民们决定举办一场区域性的节目比赛。评审委员会自愿并承诺组织有史以来最诚实的比赛。决定使用“星形”拓扑为参赛者连接计算机——即将它们全部连接到一个中央集线器。为了组织一场真正诚实的比赛，评审委员会主席下令将所有参赛者均匀地放置在中心周围，距离中心相等。为了购买网线，评审委员会联系了当地的网络解决方案供应商，要求为他们出售指定数量的等长网线。评审委员会希望电缆尽可能长，以使参赛者彼此尽可能远离。公司的电缆主管被指派执行这项任务。他知道库存中每根电缆的长度可达一厘米，而且他可以以厘米的精度切割它们，并被告知他必须切割的碎片长度。但这一次，长度不详，索主完全不解。您将通过编写一个程序来帮助 Cable Master，该程序将确定可以从库存中的电缆中切割出的电缆段的最大可能长度，以获得指定的段数。输入输入文件的第一行包含两个整数 N 和 K，用空格分隔。N (1 = N = 10000) 是库存中的电缆数量，K (1 = K = 10000) 是请求的件数。第一行后面是 N 行，每行一个数字，指定库存中每根电缆的长度（以米为单位）。所有电缆的长度至少为 1 米，最长为 100 公里。输入文件中的所有长度都以厘米精度写入，小数点后正好有两位数字。输出将 Cable Master 可以从库存中的电缆切割以获得请求的件数的最大长度（以米为单位）写入输出文件。该数字必须以厘米精度书写，小数点后恰好有两位数字。如果无法切割所需数量的每件至少一厘米长，则输出文件必须包含单个数字“0.00”（不带引号）。

---

题意：有N根绳子，它们长度分别为Li。如果从他们中切割出K条长度相同的绳子的话，这K条绳子每条最长能有多长？答案保留到小数点后两位。

---

这题我给出两种方法求解

一、二分查找

二分查找，简单说就是我们玩的数字炸弹里最常用的方法，每找一次分两半，看离最后的答案是大还是小

二、解

1.代码

这道题的代码如下（1）：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include<cmath>
#define INF 0x3f3f3f3fusing namespace std;long long N,K;
const int maxn = 1e6+10;
double L[maxn];bool C(double x)
{int num=0;for(int i=0; i<N; i++){num+=(int) (L[i]/x);}return num>=K;
}int main()
{while(cin>>N>>K){for(int i=0; i<N; i++)scanf("%lf",&L[i]);sort(L,L+N);double lb=0,ub=INF;//INF 0x3f3f3f3f <max_int 2^31for(int i=0; i<100; i++){double mid = (lb + ub)/2;if(C(mid))lb=mid;elseub=mid;}printf("%0.2f\n",floor(ub * 100) /100);}return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e5 + 100;
int n, s;
int a[N], sum[N];int main() {cin >> n >> s;for(int i=1; i<=n; i++) {cin >> a[i];sum[i] = sum[i-1] + a[i];}int ans = n;for (int i = 1; i <= n; i ++){int pos = upper_bound(a + 1, a + n + 1, sum[i] - s) - a;int len = i - pos + 1;if (len < ans) ans = len;}cout << ans << endl;return 0;	
}

2.解

代码（1）：
这份代码主要是用基本的二分查找，
用函数C二分，只要分出的份数大于所需要的份数，则true，否则false，然后再继续往不同的方向二分，变大或变小。

代码（2）：
这份代码主要是用前缀和和二分查找，运用algorithm库里的upper_bound找到比第三个形参大的第一个数的下标，用此找到len，判断出answer

---

总结

这道题对于我来说还是很难理解的，特别是第二份代码，讲解的也不是很到位，还请多多谅解

这篇关于2021-07-06 POJ1064的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---