首页 技术 正文
技术 2022年11月23日
0 收藏 558 点赞 2,798 浏览 1954 个字

Problem DescriptionProfessor Zhang has a number sequence a1,a2,…,an. However, the sequence is not complete and some elements are missing. Fortunately, Professor Zhang remembers some properties of the sequence:

1. For every i∈{1,2,…,n}, 0≤ai≤100.
2. The sequence is non-increasing, i.e. a1≥a2≥…≥an.
3. The sum of all elements in the sequence is not zero.

Professor Zhang wants to know the maximum value of a1+a2∑ni=1ai among all the possible sequences.

 InputThere are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first contains two integers n and m (2≤n≤100,0≤m≤n) — the length of the sequence and the number of known elements.

In the next m lines, each contains two integers xi and yi (1≤xi≤n,0≤yi≤100,xi<xi+1,yi≥yi+1), indicating that axi=yi.

 OutputFor each test case, output the answer as an irreducible fraction “p/q”, where p, q are integers, q>0. Sample

Sample InputSample Output
/
/

题意:

  有一个数字序列,给出数字序列的性质是:

  1.每个数最大为100,最小为0

  2.序列非递增

  3.序列总和不为0

  求出这个数列HDU5742 It's All In The Mind  数学思维题的最大值

  样例:第一行是T,表示T组测试样例,第二行是n,m。表示序列的长度和已知数的个数。下m行为xy,表示axi=yi

      第一组 长度为2,已知0个。则最大值为(100+100)/(100+100)或者(1+1)/(1+1)最大值为1。

      第二组长度为3,已知1个。已知的这一个为a3=1 。则最大值为(100+100)/(100+100+1)

思路:

  想求(a1+a2)/(a1+a2+…+an) 的最大值,只要让分母尽可能大,分子尽可能小即可。

  有两种情况,第一种为已知a1,a2。让不知道的数取最小值(不是0,因为要保证序列非递增)。

  第二种情况,不知道a1或者a2。让a1和a2取最大值(也要注意序列非递增)。

  最后用GCD求出a1+a2与序列和的最大公因数,然后取分数。

代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int gcd(int a,int b)//求最大公约数
{
if(b==)
return a;
return gcd(b,a%b);
}
int main()
{
int a[],t,m,n;
scanf("%d",&t);
while(t--)
{
int i,j,x,y,sum1=,sum2=,ans=;
int w=;
scanf("%d%d",&n,&m);
for(i=; i<=n; i++)
a[i]=-;//初始化数组为-1,因为数组从0-100,所以可以用-1来表示
for(i=; i<=m; i++)
{
scanf("%d%d",&x,&y);
a[x]=y;//将已知条件赋值
}
for(i=n; i>=; i--)//从3-n尽量取最小
{
if(a[i]==-)//如果后面没有值,说明没有非递增限制,直接赋值为w,w初始为0
a[i]=w;
else//如果已经有值,则值前面的赋值为这个值。
{
w=a[i];
}
}
if(a[]==-)/*如果a[1]没有值,则赋值为100(最大)*/
a[]=;
if(a[]==-)/*如果a[2]没有值,则与a[1]相同*/
a[]=a[];
for(i=; i<=n; i++)
sum1+=a[i];
sum2=a[]+a[];
ans=gcd(sum2,sum1);
printf("%d/%d\n",(sum2/ans),(sum1/ans));
}
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141750.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:876 阅读:5,475
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,696
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,511
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:731 阅读:4,472
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:5,389
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,268
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站