解题思路:将瓜从大到小排序,以获得最小切割次数,采用回溯算法来判断切割次数
注意事项:由于采用float定义会产生精度误差,所以采用*2的方式
参考代码:
#include
#include
#include
using namespace std;
vector
vector
int ans=31;
int m;
long sum=0;
int n;
bool cmp(int a,int b){
return a>b;
}
void dfs(int i,int count,long sum)
{
if(sum==m){
ans=min(count,ans);//找到最小次数返回
return;
}
if(sum>m||i>n||count>=ans||sum+B[i]<m)return;//减少次数,不然要超时
dfs(i+1,count,sum+M[i]);//直接买整个
dfs(i+1,count+1,sum+M[i]/2);//买半个
dfs(i+1,count,sum);//不买
}
int main()
{
long totle=0;
cin>>n>>m;
m*=2;
for(int i=0;i<n;i++)
{
cin>>M[i];
M[i]*=2;
totle+=M[i];
}//全部以两倍储存,用float容易出错
for(int i=n-1;i>=0;i--){
B[i]=B[i+1]+M[i];
}
if(totle<m){
cout<<-1;
return 0;
}
sort(M.begin(),M.end(),cmp);
dfs(0,0,sum);
if(ans!=31)cout<<ans;//如果ans的数值改变就输出,否则说明找不到,输出-1
else cout<<-1;
return 0;
}
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:1118 |
破解简单密码 (C语言代码)浏览:1768 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:646 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:592 |
简单的a+b (C语言代码)浏览:606 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:596 |
【蟠桃记】 (C语言代码)浏览:1035 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:560 |
C语言程序设计教程(第三版)课后习题12.2 (C语言代码)浏览:766 |
敲七 (C++代码)浏览:1056 |