华师一附中OI组

标题: P1577 切绳子 [打印本页]

---

作者: admin    时间: 2018-7-24 18:23
标题: P1577 切绳子
https://www.luogu.org/problemnew/show/P1577

题目描述
有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？答案保留到小数点后2位。

输入输出格式
输入格式：
第一行两个整数N和K，接下来N行，描述了每条绳子的长度Li。

输出格式：
切割后每条绳子的最大长度。

输入输出样例
输入样例#1：
4 11
8.02
7.43
4.57
5.39
输出样例#1：
2.00
说明
对于100%的数据 0<Li<=100000.00 0<n<=10000 0<k<=10000

---

作者: 吴语林    时间: 2018-7-25 14:15

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. using namespace std;
    
12. int n,k;
    
13. double a[10100],zuo,you;
    
14. char s[100];
    
15. long long check(double x)
    
16. {
    
17.         long long all=0;
    
18.         for(int i=1;i<=n;i++)
    
19.                 all+=floor(a[i]/x);
    
20.         return all;
    
21. }
    
22. int main()
    
23. {
    
24.         scanf("%d%d",&n,&k);
    
25.         for(int i=1;i<=n;i++)
    
26.                 scanf("%lf",&a[i]),you+=a[i];
    
27.         while(fabs(zuo-you)>0.0001)
    
28.         {
    
29.                 double mid=(zuo+you)/2;
    
30.                 if(check(mid)>=k) zuo=mid;
    
31.                 else you=mid;
    
32.         }
    
33.         sprintf(s+1,"%.3f",zuo);
    
34.     s[strlen(s+1)]='\0';
    
35.     printf("%s",s+1);
    
36.         return 0;
    
37. }

复制代码

---

作者: 黄煦喆    时间: 2018-8-28 21:38

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cmath>
   
4. using namespace std;
   
5. int n,k,cnt;
   
6. double a[10001],l,r,sum;
   
7. double const eps=1e-3;
   
8. int main()
   
9. {
   
10.     cin>>n>>k;
    
11.     for(int i=1;i<=n;i++)
    
12.     {
    
13.         cin>>a[i];
    
14.         sum+=a[i];
    
15.     }
    
16.     r=sum;
    
17.     while(r-l>eps)
    
18.     {
    
19.         cnt=0;
    
20.         double mid=l+(r-l)/2.0;
    
21.         if(!mid)break;
    
22.         for(int i=1;i<=n;i++)cnt+=floor(a[i]/mid);
    
23.         if(cnt>=k)l=mid+eps;
    
24.         else r=mid-eps;
    
25.     }
    
26.     printf("%.2f",l);
    
27.     return 0;
    
28. }
    
29. 
    

复制代码

---

作者: 黄煦喆    时间: 2018-8-28 21:39

黄煦喆 发表于 2018-8-28 21:38

90分程序，在进位上总有问题

---

作者: 倚窗倾听风吹雨    时间: 2018-9-1 13:44

黄煦喆 发表于 2018-8-28 21:39
90分程序，在进位上总有问题

可以先将所有长度乘100变为整数，就不存在进位问题了。

---

作者: 倚窗倾听风吹雨    时间: 2018-9-1 17:29

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. const int M=10010;
   
5. double l[M],ans;
   
6. int n,k,maxl;
   
7. bool judge(int x)
   
8. {
   
9.     int i=1,pi=0;
   
10.     for(int i=1;i<=n;i++)
    
11.     {
    
12.         int po=l[i];
    
13.         while(po-x>=0)
    
14.         {
    
15.             po-=x;pi++;
    
16.         }
    
17.     }
    
18.     if(pi>=k)return true;
    
19.     else return false;
    
20. }
    
21. int main()
    
22. {
    
23.     cin>>n>>k;
    
24.     for(int i=1;i<=n;i++)
    
25.     {
    
26.         cin>>l[i];
    
27.         l[i]=l[i]*100;
    
28.         maxl=max(maxl,int(l[i]));
    
29.     }
    
30.     int l=0,r=maxl;
    
31.     while(l<r)
    
32.     {
    
33.         int mid=l+(r-l+1)/2;
    
34.         if(judge(mid))
    
35.             l=mid;
    
36.         else r=mid-1;
    
37.     }
    
38.     ans=double(l)/100;
    
39.     cout<<fixed<<setprecision(2)<<ans<<endl;
    
40.     return 0;
    
41. }
    

复制代码

---

作者: admin    时间: 2018-9-2 17:58
  if(pi>=k)return true;
    else return false;  
其实可以写成  return pi>=k完全等价 毫无违和感

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2