Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:把下界直接写成0的沙茶飘过~

Posted by _paul_zhou at 2017-09-24 13:23:53 on Problem 3273
In Reply To:把下界直接写成0的沙茶飘过~ Posted by:wangjunyong at 2012-04-28 17:41:16
> 应该是最大值
下界写成0也可以,在check的时候判断一下就可以。  

//------------------------------------ac-----------------------------------------------
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <bitset>
#include <vector>   
#include <sstream>
#include <assert.h> 
#include <cstdlib>  
#include <algorithm>
using namespace std;  
typedef long long  ll;
typedef pair<ll,ll> pll;
#define fori(i,l,u) for(ll (i)=(ll)(l);(i)<=(ll)(u);++(i))
#define ford(i,l,u) for(ll (i)=(ll)(l);(i)>=(ll)(u);--(i)) 
#define fir first
#define sec second
const ll inf=0x3fff3fff3fff3fffll;

int n,m;
const ll maxn=1e5+10;
int a[maxn]; 
bool check(int x){
  int cnt=1,t=0;
  fori(i,1,n){
    if(t+a[i]<=x) t+=a[i];
    else {

      cnt++;
      t=a[i];
      if(t>x) return false;
    }
  }
  return cnt<=m;
}

void solve(){
  // int v=0,maxv=0;
  // fori(i,1,n) v=max(v,a[i]),maxv+=a[i];
  int lo=0,hi=1e9+10;
  int ret=0;
  while(lo<=hi){ 
    int mid=(lo+hi)/2;
    if(check(mid)){
      ret=mid;
      hi=mid-1;
    } else {
      lo=mid+1;
    }
  }
  printf("%d\n",ret);
}

int main()
{
  ios::sync_with_stdio(false); 
  // freopen("local.in","r",stdin);  
  while(scanf("%d%d",&n,&m)!=EOF){
    fori(i,1,n) scanf("%d",&a[i]);
    solve();
  }

  return 0;
}




Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator