日暮途远

用户名：uq_31085418554

访问量：653

签　名：

等　　级
排　　名	2746
经　　验	2089
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

增添战力-题解(C语言代码)
浏览：423

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

增添战力-题解(C语言代码)

　　作者: 日暮途远　　　　发表时间：2020-03-22 12:48:13 浏览：423　|　评论：1　

原题链接：增添战力

本题可以使用贪心算法求解，我的计算方法是：
1.将输入的各豪杰战力排个序（我是插入排序从小到大排的）；
2.比较两座城池所需豪杰数量，将战力最靠强的豪杰分配到需求量较少的城池去，然后将剩下战力最强的分配到另外一个城池去。为什么这样分配呢，这涉及到加权，分析如下：
假设A城需2人,B城需3人，A城派去的战力为x1，x2，B城派去的战力为x3,x4,x5，则
A城平均战力：(x1+x2)/2;
B城平均战力：(x3+x4+x5)/3;
平均值之和(结果)：(x1+x2)/2+(x3+x4+x5)/3=x1/2+x2/2+x3/3+x4/3+x5/3;
不难看出，想让结果最大，当然是让战力越强的占据更多权重对吧。x1,x2只用除以2，所以理应把最大的先分给A，也就是需求较少的一城。也就是需求越小，分配过去的战力占结果的权重越大；
延伸：本题不像其他一些背包问题，豪杰都是一个一个的，在某些背包问题中，在考虑所取物品价值的同时，还要额外考虑物体本身的重量以及背包的容量，本问题没有涉及，所以贪心算法的解是整体最优解
代码如下：
#include <stdio.h>
int main()
{
int n,n1,n2,i,j,k;//n是总豪杰数量，n1，n2是两座城分别需要的豪杰数量
double sum1=0,sum2=0,sum;//这里数据类型最好是double，float会报答案错误
scanf("%d %d %d",&n,&n1,&n2);
int a[n],b[n];//b数组用来存储将各豪杰战力从小到大排序的结果
for(i=0;i<n;i++)
      scanf("%d",&a[i]);
    b[0]=a[0];//以下是插入排序
	for(i=1;i<n;i++)
	{
	    for(j=0;j<i;j++)
        {
            if(a[i]<=b[j]) break;
            else continue;
        }
            if(i==j) b[j]=a[i];
            else
            {
                for(k=i;k>j;k--)
                    b[k]=b[k-1];
                b[j]=a[i];
            }
	}//以上是插入排序
if(n1<n2){//贪心法求解
    for(i=n-1;i>n-1-n1;i--)
        sum1+=b[i];
    for(i=n-1-n1;i>n-1-n1-n2;i--)
        sum2+=b[i];
}
else{
    for(i=n-1;i>n-1-n2;i--)
        sum2+=b[i];
    for(i=n-1-n2;i>n-1-n1-n2;i--)
        sum1+=b[i];
}
    sum=sum1/n1+sum2/n2;
    printf("%.6lf",sum);
return 0;
}

以上仅个人看法，如果有错误的地方，请直接指明，共同进步，谢谢

0.0分

2 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

莫阑珊

不错了这个题目题意最难理解了hh，时间限制倒没那么严格，冒泡排序也行

2021-12-03 23:01:12

日暮途远

TA的其他文章

你可能喜欢

C语言训练-计算一个整数N的阶乘（C语言代码）

用筛法求之N内的素数。（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

点我有惊喜！你懂得！

增添战力-题解(C语言代码)

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

a+b

关于float，double变量的几点说明

企业奖金发放（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

日暮途远

TA的其他文章

你可能喜欢

C语言训练-计算一个整数N的阶乘 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

点我有惊喜！你懂得！

增添战力-题解(C语言代码)

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

a+b

关于float，double变量的几点说明

企业奖金发放 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言训练-计算一个整数N的阶乘（C语言代码）

用筛法求之N内的素数。（C语言代码）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

企业奖金发放（C语言代码）