jsoi
题目描述
奶酪和pizza一样，是一小块扇形的固体。在奶酪从工厂里生产出来的时候，一共有4种形状，编号为1～4，分别是圆心角为72º，144º，216º，288º的扇形。奶酪的盒子是圆形的，半径和奶酪的半径一致。也就是说，一块1号奶酪和一块4号奶酪可以恰好装入一个盒子，一块2号奶酪和一块3号奶酪可以恰好装入一个盒子。 你的任务是写一个程序，计算给定的奶酪最多可以装满几个盒子。
1～4号奶酪的数量，都在0～100之内
贪心
由于每步都采用同样的、简单的策略，无论从代码的实现上，还是从时间复杂度上看，都是相当好的选择。
贪心算法如果设计的到位，可以保证在几乎所有情况得到正解答案。
进一步地，当局部最优解可以推出全局最优解时，贪心就是正解答案。
四种奶酪分别为：72º、144º、216º、288º 。
首先考虑可以组合的方法有以下几种：
4+1、3+2、3+1+1、2+2+1、2+1X3、1X5
那么究竟应该先用哪种方案？如果采用类似NOIP乌龟棋的动规，很大可能是会超时。采用搜索似乎效率更低
采取贪心算法：优先选择角度大的奶酪进行组合。
分析：若先使用小的奶酪，则需要大量的小号奶酪，使得之后与大号的匹配时数量不足。
贪心未必要严谨，在实际情况中可以不用数学语言来证明。
它所拥有的简洁性和自由度是其它算法所不能达到的。
若要证明贪心的正确性，需要证明局部全优可以造成全局最优。
贪心老公式：能放就放，大的顺序在前。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
using namespace std;
int main()
{
int a,b,c,d,ans=0;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(d>a)
ans=ans+a,a=0;
else
ans=ans+d,d=0;
if(c>b)
ans=ans+b,b=0;
else
ans=ans+c,c=0;
while(b>=2&&a>=1)
ans++,b=b-2,a--;
while(a>=2&&c>0)
ans++,c--,a=a-2;
while(a>=3&&b>0)
ans++,b--,a=a-3;
printf("%d\n",ans+a/5);
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
