UVA-1614 Hell on the Markets(贪心+推理) (有待补充)

时间:2022-01-17 03:56:48

题目大意:一个整数序列a,1≤a[i]≤i。问能否通过在一些元素前加上负号,使得整个序列和为0。

题目分析:贪心。贪心策略:每次都先选最大的元素加负号(或保留,不加负号)。

     贪心依据:对于1≤a[i]≤i,1~sum[i]总能表示出来。

       贪心依据证明:用数学归纳法证明,当i=1时,显然成立。假设当i=k时,也成立。当i=k+1时,(先证明到这儿,有空再补)。

代码如下:

# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; struct Num
{
int val,id;
bool operator < (const Num &a) const {
return val<a.val;
}
};
Num num[100005];
int n,mark[100005]; void solve(int u)
{
for(int i=n-1;i>=0;--i){
if(u-num[i].val==0){
mark[num[i].id]=1;
return ;
}else if(u-num[i].val>0){
u-=num[i].val;
mark[num[i].id]=1;
}
}
} int main()
{
long long sum;
while(scanf("%d",&n)==1)
{
memset(mark,0,sizeof(mark));
sum=0;
for(int i=0;i<n;++i){
scanf("%d",&num[i].val);
num[i].id=i;
sum+=num[i].val;
}
if(sum&1){
printf("No\n");
continue;
}
sort(num,num+n);
solve(sum/2);
printf("Yes\n");
for(int i=0;i<n;++i)
printf("%d%c",mark[i]?1:-1,(i==n-1)?'\n':' ');
}
return 0;
}

  

UVA-1614 Hell on the Markets(贪心+推理) (有待补充)的更多相关文章

  1. UVa 1614 Hell on the Markets &lpar;贪心&plus;推理&rpar;

    题意:给定一个长度为 n 的序列,满足 1 <= ai <= i,要求确实每一个的符号,使得它们和为0. 析:首先这一个贪心的题目,再首先不是我想出来的,是我猜的,但并不知道为什么,然后在 ...

  2. UVA 1614 - Hell on the Markets 奇怪的股市(贪心,结论)

    先证明一个结论吧,对于1≤ai≤i+1,前面ai个数一定可以凑出1~sum[i]中的任意一个数. 对于i=1显然成立, 假设对于i=k结论成立,那么对于i=k+1来说,只要证明sum[k]+i,1≤i ...

  3. UVA - 1614 Hell on the Markets(奇怪的股市)(贪心)

    题意:输入一个长度为n(n<=100000)的序列a,满足1<=ai<=i,要求确定每个数的正负号,使得所有数的总和为0. 分析: 1.若总和为0,则未加符号之前,所有数之和必为偶数 ...

  4. UVA 1614 - Hell on the Markets

    题意: 输入n个数,第i个数ai满足1≤ai≤i.对每个数添加符号,使和值为0. 分析: 排序后从最大的元素(假设为k)开始,凑出sum/2即可.用去掉了k的集合,一定可以凑出sum/2 - a[k] ...

  5. uva 1614奇怪的股市(归纳法证明,贪心)

    uva 1614奇怪的股市(归纳法证明,贪心) 输入一个长度为n的序列a,满足\(1\le a_i\le i\),要求确定每个数的正负号,使得所有数的总和为0.例如a={1, 2, 3, 4},则4个 ...

  6. Uva 11729 Commando War (简单贪心)

    Uva 11729  Commando War (简单贪心) There is a war and it doesn't look very promising for your country. N ...

  7. uva 1153 顾客是上帝(贪心)

    uva 1153 顾客是上帝(贪心) 有n个工作,已知每个工作需要的时间q[i]和截止时间d[i](必须在此前完成),最多能完成多少个工作?工作只能串行完成,第一项任务开始的时间不早于时刻0. 这道题 ...

  8. 【uva 1614】Hell on the Markets(算法效率--贪心)

    题意:有一个长度为N的序列A,满足1≤Ai≤i,每个数的正负号不知.请输出一种正负号的情况,使得所有数的和为0.(N≤100000) 解法:(我本来只想静静地继续做一个口胡选手...←_← 但是因为这 ...

  9. UVA - 1614 Hell on the Market(贪心)

    Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu Submit Status Descript ...

随机推荐

  1. nodejs express template &lpar;模版&rpar;的使用 &lpar;ejs &plus; express&rpar;

    var app=require("express").createServer(); app.set("view engine","ejs" ...

  2. 使用Css截取字符串

    white-space:nowrap; /* 禁止自动换行 */ overflow:hidden; /* 隐藏溢出的内容 */ text-overflow:ellipsis; /* 溢出文本使用... ...

  3. JAVA&lowbar;FastJson

    package com.qf.mobiletrain01; import java.util.List; import com.alibaba.fastjson.JSON; class Student ...

  4. Flume简介与使用(二)——Thrift Source采集数据

    Flume简介与使用(二)——Thrift Source采集数据 继上一篇安装Flume后,本篇将介绍如何使用Thrift Source采集数据. Thrift是Google开发的用于跨语言RPC通信 ...

  5. Windows Redis默认配置文件,Redis配置不生效解决方案

    Windows Redis默认配置文件,Redis配置不生效解决方案, Windows Redis自启动配置不生效解决方案,Windows Redis增加自动启动服务 >>>> ...

  6. 关于java中反射的小结

    一.Class 1. Class是一个类,封装了当前对象所对应的类的信息 2.小写class表示是一个类类型,大写Class表示这个类的名称 3.对于每个类而言,JRE 都为其保留一个不变的 Clas ...

  7. luogu P3295 &lbrack;SCOI2016&rsqb;萌萌哒

    传送门 题目条件"两个子串\(S[l_1,r_1],S[l_2,r_2]\)完全相同"等价于\(\forall i \in[0,r_1-l_1+1],S_{l1+i}=S_{l_2 ...

  8. python:3种爬虫的优缺点

                                                                 性能对比            爬取方法            性    能 ...

  9. 一个python脚本解决安装mq的依赖问题

    import tarfile import sys,os from _utils.patrol2 import run_cmd import zipfile def get_version(filen ...

  10. 0&period; 资料官网【从零开始学Spring Boot】

    [视频&交流平台] àSpringBoot视频 http://study.163.com/course/introduction.htm?courseId=1004329008&utm ...