?1?/*
?2??*因為可以大致估算出答案的上下界所以可以使用二分法對答案進行逼近
?3??*對于給定的數列，對多了一產生sum/m條項鏈，這個就是答案的上界，下界自然就是0
?4??*然后驗證某一個解的正確性
?5??*如果ans大于某一種珍珠i的個數，那么，此種珍珠就選擇ans個，如果選擇多于ans個
?6??*就會出現i珍珠在一條項鏈上出現多余一個的情況。如果某種珍珠的個數多于ans個那
?7??*么就將其全部選入。此時可能出現兩種情況，一種是剛剛好可以組成ans條項鏈，
?8??*另一種就是可以組成多余ans條的項鏈，那么tem就會大于m*ans
?9??*剩下的就是二分的使用了
10??*
11??*/
12?
13?
14?#include?<iostream>
15?#include?<memory.h>
16?using?namespace?std;
17?int?n;
18?int?m;
19?int?pr[1001];
20?int?check(int?ans)
21?{
22?????????int?tem=0;
23?????????for(int?i=0;i<n;i++)
24?????????????????if(pr[i]<ans)
25?????????????????????????tem+=pr[i];
26?????????????????else
27?????????????????????????tem+=ans;
28?????????if(tem>=m*ans)
29?????????????????return?1;
30?????????else
31?????????????????return?0;?????
32?}
33?int?main()
34?{
35?????????while(cin>>n,n!=0)
36?????????{
37?????????????????int?sum=0;
38?????????????????for(int?i=0;i<n;i++)
39?????????????????{
40?????????????????????????cin>>pr[i];
41?????????????????????????sum+=pr[i];
42?????????????????}
43?????????????????cin>>m;
44?????????????????int?low=0;
45?????????????????int?ans=0;
46?????????????????while(low<=sum)
47?????????????????{
48?????????????????????????int?mid=(low+sum)/2;
49?????????????????????????if(check(mid))
50?????????????????????????{
51?????????????????????????????????ans=mid;
52?????????????????????????????????low=mid+1;
53?????????????????????????}
54?????????????????????????else
55?????????????????????????????????sum=mid-1;
56?????????????????}
57?????????????????cout<<ans<<endl;
58?????????}
59?}

轉載于:https://www.cnblogs.com/congzc/archive/2011/05/20/2329951.html

總結

以上是生活随笔為你收集整理的2015. A New Year Gift的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。