1月11日星期天9:00-12:00

T1242 网线主管

🧠 题意解析

你有 N 条网线，每条长度为浮点数（精确到厘米，保留两位小数），要从这些网线中裁剪出 恰好 K 条长度相同的网线，并且：

每条网线都可以被多次裁剪；

所有裁剪出的网线长度相等；

裁判想让这条网线 尽可能长。

✨ 核心思路：二分长度

我们要找出一个最大长度 L，满足：

所有原始网线总共能切出 K 条长度为 L 的线段

由于结果精确到厘米（0.01米），我们可以：

把所有长度统一转换为整数厘米单位（即把 100.00 变成 10000）

最后输出时再转为小数，保留两位

#include<bits/stdc++.h>
using namespace std;
int n,k,num[11000],l=1,r,mid;
// x 是我们找到的网线长度
// 如果该网线长度裁剪的数量没有K段 说明长度过长 向左找
// 如果该网线长度裁剪的数量大于K段 说明长度过短 等于K段也向右找保证网线长度尽可能长 向右找
bool check(int x) {
    int jishu = 0;
    for (int i =1;i<=n;i++) {
        jishu+= num[i]/x;
    }
    return jishu>=k;
}
int main() {
    cin>>n>>k;
    for (int i=1;i<=n;i++) {
        double a;
        cin>>a;
        num[i] = a*100;
        r = max(r,num[i]);
    }
    while (l<=r) {
        mid = l+r>>1;
        if (check(mid)) {
            l = mid+1;
        }else {
            r = mid-1;
        }
    }
    printf("%.2lf",(l-1)*0.01);
    return 0;
}

T1243 月度开销

📌 题目理解：
农夫约翰要把 N 天的花销分成 M 个月，每个月花销之和不同。

他希望这 M 个月中花钱最多的那个月，花得尽量少。我们要帮他想一个分配方案，让花销最多的那个月也不太高！

询问:
m为什么情况下能让花钱最多的那个月最少? 给每天开销算一个月就是n=m 这样最大开销月的最小值就是每月的最大值

Left为每个月的最大值 right 为每个月的花销和

🧠 思路分析
我们要做的是：把一个数组分成 M 段，使得每段的和的最大值最小

这个问题的经典模型是：「二分最大值」+「贪心验证」

✅ 步骤一：二分答案
我们要找的答案是一个数字，这个数字代表每个月最多能花多少钱，并且我们可以按照这个标准把整个数组分成 M 段。

我们可以二分这个“最大允许的月开销”，比如：

假设最大开销是 10 万元，看能不能把这些天分成 M 段，每段不超过 10 万

如果可以，再试试更小的值

如果不行，说明太紧了，需要放宽点

✅ 步骤二：贪心判断是否可行
对于一个候选最大开销值 x，我们要判断能不能把 N 天分成 M 段，每段的和都 ≤ x。

用贪心的方法遍历数组：x

累加天数花费

一旦当前段的和超过了 x，就切一段，新开一个月

最后看看总共用了多少个月（段）

如果用的段数 ≤ M，说明这个 x 是可以接受的。

#include<bits/stdc++.h>
using namespace std;
int n,m,num[110000],l=1,r,mid;
// x 是我们找到的最大开销月的金额(假设)
// 如果该最大开销月分的月份小于m个月 说明最大开销月过大 向左找  等于m个月
// 如果该最大开销月分的月份大于m个月 说明最大开销月过小 向右找
bool check(int x) {
    int jishu=1,cnt=0;
    for (int i=1;i<=n;i++) {
        cnt+=num[i];
        if (cnt>x) {
            jishu++;
            cnt = num[i];
        }
    }
    return jishu<=m;
}
int main() {
  //n天数  m周期数
    cin>>n>>m;
    for (int i=1;i<=n;i++) {

        cin>>num[i];
        l = max(l,num[i]);
        r+=num[i];
    }
    while (l<=r) {
        mid = l+r>>1;
        if (check(mid)) {
            r = mid-1;
        }else {
            l = mid+1;
        }
    }
    cout<<l;
    return 0;
}

T1244 和为给定数

思路一:

排序好数组循环一个数,去二分查找另外一个数

判断查找到的数字是否等于X 并且防止没有找到到边界外

找不到输出No

思路二:

排序好数组用l r指向我们要找的两个数

如果想加起来大了移动右指针小了... 直到第一个等于的

#include<bits/stdc++.h>
using namespace std;
int n,num[100100],m;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
      cin>>num[i];
    }
    cin>>m;
    sort(num+1,num+1+n);
    for (int i=1;i<=n;i++) {
        int x = m-num[i];
        int *p = lower_bound(num+1,num+1+n,x);
        if (*p==x&&p-num!=n+1) {
            cout<<num[i]<<" "<<x;
            return 0;
        }
    }
    cout<<"No";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,num[100100],m;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
      cin>>num[i];
    }
    cin>>m;
    sort(num+1,num+1+n);
    for (int i=1;i<=n;i++) {
        int x = m-num[i];
        int *p = lower_bound(num+1,num+1+n,x);
        if (*p==x&&p-num!=n+1) {
            cout<<num[i]<<" "<<x;
            return 0;
        }
    }
    cout<<"No";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, a[110000];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> m;
    sort(a, a + n);
    int l = 0, r = n - 1;
    while (l < r) {
        if (a[l] + a[r] > m) {
            r--;
        } else if (a[l] + a[r] < m) {
            l++;
        } else {
            cout << a[l] << " " << a[r];
            return 0;
        }
    }
    cout << "No";
    return 0;
}

T1242 网线主管#

T1243 月度开销#

T1244 和为给定数#

#

T1242 网线主管

T1243 月度开销

T1244 和为给定数