HDU5742:It's All In The Mind(模拟+贪心 )
2024-10-18 06:30:12
题意:
给出n和m,表示n个数,之后会给出m个下标xi和值yi,a[xi]=yi,n个数是不下降的,且总和>0,要使得(x1+x2)/∑(xi)最大。
分析:
尽可能使得前两个数最大,其他数尽可能小即可。
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
int a[];
int T;
int n, m, x1,x2, y1,y2; inline int gcd(int a, int b){return b == ? a : gcd(b, a % b);} int main(){
scanf("%d ", &T);
loop: while (T--){
scanf("%d %d ", &n, &m);
memset(a,, sizeof a);
x1=;
scanf("%d %d",&x2,&y2);
if(x2==)
{
a[]=a[]=y2;x1=x2;
}
else
{
a[x2]=y2;
if(x2<=) rep(i,,x2-) a[i]=;
else{a[]=a[]=;rep(i,,x2-) a[i]=y2;} x1=x2;
}
rep(i,,m)
{
scanf("%d %d", &x2, &y2);
a[x2]=y2;
if(i<=m)
{
if(x1+==) rep(j,,x2-) a[j]=y2;
else rep(j,x1+,x2-) a[j]=y2;
}
x1=x2;
}
rep(j,x1+,n) a[j]=;
//rep(i,1,n) printf("a[%d]=%d\n",i,a[i]);
if (n ==){ puts("1/1"); goto loop;}
int sum =;
rep(i,, n) sum += a[i];
//printf("a[1]+a[2]=%d sum=%d\n",a[1]+a[2],sum);
int g = gcd(a[]+a[], sum);
printf("%d/%d\n", (a[]+a[])/ g, sum / g);
}
return;
}
最新文章
- 如何使CEF支持Flash
- shell命令快捷键
- Django笔记-常见错误整理
- pod install 错误 - incompatible character encodings: UTF-8 and ASCII-8BIT
- fir.im Weekly - 2016 移动开发技术大回顾
- MySQL用命令行导出数据库
- 关于git的文件内容冲突解决
- 转:PO BO VO DTO POJO DAO概念及其作用
- (原)ubuntu上安装Torch7及nn及dpnn
- MVC新语法匿名方法
- 翻译一篇文章:It&#39;s Difficult to Grow a Test Developer(成为测试开发工程师的艰辛)
- JEECG中的模糊查询
- jmeter压测数据库,抓包工具,python基础
- linux清空文件内容的几种方式与区别
- VisualStudio移动开发(C#、VB.NET)Smobiler开发平台——GifView控件的使用方式
- 【转载】 “强化学习之父”萨顿:预测学习马上要火,AI将帮我们理解人类意识
- python的if条件判断
- beautifulsoup之CSS选择器
- fatal error C1010: unexpected end of file while looking for precompiled header. Did you forget to add &#39;#include ";stdafx.h";&#39; to your source?
- jQuery事件之传递参数