Description
HYSBZ 開學(xué)了！今年HYSBZ 有n 個男生來上學(xué)，學(xué)號為1…n，每個學(xué)生都必須參加軍訓(xùn)。在這種比較墮落的學(xué)校里，每個男生都會有Gi 個女朋友，而且每個人都會有一個欠扁值Hi。學(xué)校為了保證軍訓(xùn)時教官不會因為學(xué)生們都是人生贏家或者是太欠扁而發(fā)生打架事故，所以要把學(xué)生們分班，并做出了如下要求：

1.分班必須按照學(xué)號順序來，即不能在一個班上出現(xiàn)學(xué)號不連續(xù)的情況。

2.每個學(xué)生必須要被分到某個班上。

3.每個班的欠扁值定義為該班中欠扁值最高的那名同學(xué)的欠扁值。所有班的欠扁值之和不得超過Limit。

4.每個班的女友指數(shù)定義為該班中所有同學(xué)的女友數(shù)量之和。在滿足條件1、2、3 的情況下，分班應(yīng)使得女友指數(shù)最高的那個班的女友指數(shù)最小。

請你幫HYSBZ 的教務(wù)處完成分班工作，并輸出女友指數(shù)最高的班級的女友指數(shù)。

輸入數(shù)據(jù)保證題目有解。

Input
第一行僅2 個正整數(shù)n, Limit，分別為學(xué)生數(shù)量和欠扁值之和的上限。

接下來n 行每行2 個正整數(shù)Hi，Gi，分別為學(xué)號為i 的學(xué)生的欠扁值和女友數(shù)。

Output
僅1 個正整數(shù)，表示滿足分班的條件下女友指數(shù)最高的班級的女友指數(shù)。

Sample Input
4 6

4 3

3 5

2 2

2 4

Sample Output
8

【樣例解釋】

分班按照（1,2），（3,4）進行，這時班級欠扁值之和為4+2=6<=Limit，而女友指數(shù)最高的班級為(1,2)，為8。容易看出該分班方案可得到最佳答案。

Data Constraint
對于20%的數(shù)據(jù)：n，Limit<=100
對于40%的數(shù)據(jù)：n<=1000
對于100%的數(shù)據(jù)：1<=n，Gi<=20000，1<=Hi，Limit<=10^7
.
.
.
.
.

分析

題目是求最大值最小，所以應(yīng)該二分。

.
.
.
.
.

程序：

#include <iostream> #include <string.h> using namespace std; long long b[20001],f[20002],lim,mid,w,ans; int n,k,t,tj,q[20001],next[20001],a[20001],c[20001];int work(int x) {int l=x,r=n,mid1=(l+r)/2;while (l<r){mid1=(l+r)/2;if (b[mid1]-b[x-1]>=mid) r=mid1; else l=mid1+1;}return l; }bool check() {memset(f,127,sizeof(f));f[1]=0;for (int i=1;i<=n;i++){int x=i,w=q[x],k=work(i);if (b[k]-b[i-1]>mid) k--;while (x<=k){f[x]=min(f[x],f[i]+w);w=q[x];x=next[x];}f[k+1]=min(f[k+1],f[i]+w);}if (f[n+1]>lim) return 0; else return 1; }int main() {cin>>n>>lim;for(int i=1;i<=n;i++){int x;cin>>q[i]>>x;b[i]=b[i-1]+x;}tj=1;a[1]=n+1;c[1]=2147483647;for (int i=n;i;i--){while (q[i]>=c[tj])tj--;next[i]=a[tj];tj++;c[tj]=q[i];a[tj]=i;}int l=1,r=b[n];ans=b[n];while (l<=r){mid=(l+r)/2;if (check()){if (mid<ans) ans=mid;r=mid-1;}else l=mid+1;}cout<<ans; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499915.html

總結(jié)

以上是生活随笔為你收集整理的【NOIP2013模拟联考5】军训(training)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。