洛谷P1281 书的复制

二分

 

1 #include 
     
        2 #define For(i,j,k) for(int i=j;i<=k;i++)  3 using namespace std ;  4  5 const int N = 511,M = 511 ;  6 int a[N],L[M],R[M] ;  7 int n,k,MAX,num ;  8 struct node{ 9     int l,r ; 10 }ans[N] ;11 12 inline int read() 13 {14     int x = 0 , f = 1 ; 15     char ch = getchar() ; 16     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 17     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 18     return x * f ;  19 }20 21 inline bool check(int mid) 22 {23     int sum = 0 ; 24     num = 0 ; 25     ans[++num].l = 1 ; 26     For(i,1,n) {27         if(sum+a[i] > mid) 28             ans[num].r = i-1 ,ans[++num].l = i,sum = 0 ; 29         sum+=a[i] ;  30     }31     ans[num].r = n ; 32     return num <= k ; 33 }34 35 inline void work() 36 {37     int l = 0,r = MAX ; 38     while(l
      
       >1 ; 40         if(check(mid)) 41             r = mid ; 42         else 43             l = mid + 1 ; 44     }45     check(r) ; 46     for(int i=k;i>=1;i--) 47         printf("%d %d\n",n-ans[i].r+1,n-ans[i].l+1) ; 48 }49 50 int main() 51 {52     n = read() ; k = read() ; 53     For(i,1,n) a[i] = read(),MAX+=a[i] ; 54     For(i,1,n/2) swap(a[i],a[n-i+1]) ; 55     work() ; 56     return 0 ; 57 }