新生37

奖品，密码，吃萝卜

奖品：

题目描述

托塔李天王的三太子那吒，本领高强，他要赶在奥林匹克运动会之际，开一个头脑 奥林匹克比赛，获胜者的奖品就是经过提炼后的“氦-3”晶结体；该物质在月球上大量 存在，是一种无色、无味的氦气同位素，它在核聚变研究中有重要作用。氦-3还是一种 绝对清洁的能源，因为它本身不带放身性，因此不会产生任何放射性废料。可是如果从 月球上将该晶体运回地球呢？那吒说：用我的肚兜吧！当然他的肚兜易受太阳风等因素 的影响，载重量不能超过k（1<=k<=100000），超过这个值，肚兜就不会飞了；这个k值 那吒会告诉你的，同时还会告诉你每一个晶体的重量。 你的任务是使这个肚兜一次能运回更多的晶体。

输入

有两行 第一行有两个正整数n和k，用一个空格隔开。表示有n个晶体，肚兜最大载重量为k。 第二行有n个不超过10000的正整数，分别表示n个晶体的重量，数与数之间用一个空 格隔开。

输出

只有一行，该行只有一个正整数，表示那吒的肚兜一次能运回 的晶体重量的最大值。

样例输入 (33条消息) 吃萝卜 解题报告【二分答案】_xiaoruihang的博客-CSDN博客

这个题求的是最小的最大值，像什么最小的最大值，最大的最小值用二分来写

就是用二分来查找你要的那个答案

因此可以看出，此题的用意是让我们查找到一个合适的数,成为最大值，并且让这个最大值最小。

#include
using namespace std;
const int N=1e5;
int a[N];
int n,m;
int check(int x)
{
    int sum=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i];
        if(sum>x)
        {
            cnt++;
            sum=a[i];
        }
    }
    cnt++;
    if(cnt>m) return 0;
    else return 1;
} 
int main(){
    cin>>n>>m;
    int l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        l=max(l,a[i]);
        r+=a[i];
    }
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<endl;
    return 0;
}#include
using namespace std;
const int N=1e5;
int a[N];
int n,m;
int check(int x)
{
    int sum=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i];
        if(sum>x)
        {
            cnt++;
            sum=a[i];
        }
    }
    cnt++;
    if(cnt>m) return 0;
    else return 1;
} 
int main(){
    cin>>n>>m;
    int l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        l=max(l,a[i]);
        r+=a[i];
    }
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<endl;
    return 0;
}