今年有 n 場(chǎng) ACM-ICPC 競(jìng)賽，小明每場(chǎng)都有資格參加。第 i 場(chǎng)競(jìng)賽共有 b[i] 道題。小明預(yù)測(cè)第 i 場(chǎng)他能做出 a[i] 道題。為了讓自己看著更“大佬”一些，小明想讓自己平均做出的題數(shù)越大越好，也就是最大化大佬度，大佬度的定義如下：
為了達(dá)到這個(gè)目的，小明決定放棄 k 場(chǎng)比賽的參賽資格。請(qǐng)求出最大的大佬度。
例如有 3 場(chǎng)小型比賽，題數(shù)分別是 5 題、1 題、6 題，小明預(yù)測(cè)自己分別能做出 5 題、0題、2題。如果每場(chǎng)都參加，那么大佬度是 ，看著不怎么大佬。不過，如果放棄第 3 場(chǎng)比賽，那么大佬度就是 ?，看著更加大佬了。
Input
輸入測(cè)試文件含有多組測(cè)試，每組有 3 行。第一行有 2 個(gè)整數(shù)， 1 ≤ n ≤ 1000 和 0 ≤ k < n。第二行有 n 個(gè)整數(shù)，即每個(gè) a[i]。第三行含有 n 個(gè)正整數(shù) b[i]。保證 0 ≤ a[i] ≤ b[i] ≤ 1, 000, 000, 000。文件末尾由 n = k = 0 標(biāo)識(shí)，并且不應(yīng)該被處理。
Output
對(duì)于每組測(cè)試數(shù)據(jù)，輸出一行整數(shù)，即放棄 k 場(chǎng)比賽后可能的最高大佬度。大佬度應(yīng)該舍入到最近的整數(shù)。
Sample Input
3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0
Sample Output
83
100
Hint

為了避免舍入誤差帶來的二義性，所有答案與除法邊界相差至少 0.001 （例如答案永遠(yuǎn)不可能出現(xiàn) 83.4997）。

#include <iostream> #include <algorithm> #include <cstdio> using namespace std; int main() {int n,k;while(scanf("%d%d",&n,&k)&&n){double a[1000],b[1000];for(int i=0;i<n;++i)scanf("%lf",&a[i]);//能做for(int i=0;i<n;++i)scanf("%lf",&b[i]);//有多少double low=0.0,high=100.0,mid,ant;while(high-low>0.00001){double c[1000];ant=0;mid=low+(high-low)/2.0;for(int i=0;i<n;++i)c[i]=a[i]-mid*b[i];sort(c,c+n);for(int i=k;i<n;++i)ant+=c[i];if(ant>0)low=mid;elsehigh=mid;}printf("%.0f\n",mid*100);// cout<<mid<<endl;}return 0; }開始只用了二分搜索，TLE了

#include <iostream> #include <algorithm> #include <cstdio> using namespace std; int main() {int n,k;while(scanf("%d%d",&n,&k)&&n){int a[1000],b[1000];int c[1000];for(int i=0;i<n;++i){scanf("%d",&a[i]);//能做c[i]=i;}for(int i=0;i<n;++i)scanf("%d",&b[i]);//有多少double low=0.0,high=100,mid,ant=0;while(high-low>0.1){mid=low+(high-low)/2.0;do{double aa=0,bb=0,ans;for(int i=0;i<n-k;++i){aa+=a[c[i]];// cout<<c[i]<<' ';}// cout<<endl;for(int i=0;i<n-k;++i)bb+=b[c[i]];ans=100*(1.0*aa/bb)*1.0;if(ans>ant){ant=ans;// cout<<ant<<endl;}}while(next_permutation(c,c+n));if(ant>=mid)low=mid;elsehigh=mid;}printf("%.0lf\n",ant);//cout<<ant<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj2976Dropping tests (二分搜索+还是涉及昨天遇见的o1分数规划）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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