题目大意:一个整数序列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(贪心+推理) (有待补充)的更多相关文章
-
UVa 1614 Hell on the Markets (贪心+推理)
题意:给定一个长度为 n 的序列,满足 1 <= ai <= i,要求确实每一个的符号,使得它们和为0. 析:首先这一个贪心的题目,再首先不是我想出来的,是我猜的,但并不知道为什么,然后在 ...
-
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 ...
-
UVA - 1614 Hell on the Markets(奇怪的股市)(贪心)
题意:输入一个长度为n(n<=100000)的序列a,满足1<=ai<=i,要求确定每个数的正负号,使得所有数的总和为0. 分析: 1.若总和为0,则未加符号之前,所有数之和必为偶数 ...
-
UVA 1614 - Hell on the Markets
题意: 输入n个数,第i个数ai满足1≤ai≤i.对每个数添加符号,使和值为0. 分析: 排序后从最大的元素(假设为k)开始,凑出sum/2即可.用去掉了k的集合,一定可以凑出sum/2 - a[k] ...
-
uva 1614奇怪的股市(归纳法证明,贪心)
uva 1614奇怪的股市(归纳法证明,贪心) 输入一个长度为n的序列a,满足\(1\le a_i\le i\),要求确定每个数的正负号,使得所有数的总和为0.例如a={1, 2, 3, 4},则4个 ...
-
Uva 11729 Commando War (简单贪心)
Uva 11729 Commando War (简单贪心) There is a war and it doesn't look very promising for your country. N ...
-
uva 1153 顾客是上帝(贪心)
uva 1153 顾客是上帝(贪心) 有n个工作,已知每个工作需要的时间q[i]和截止时间d[i](必须在此前完成),最多能完成多少个工作?工作只能串行完成,第一项任务开始的时间不早于时刻0. 这道题 ...
-
【uva 1614】Hell on the Markets(算法效率--贪心)
题意:有一个长度为N的序列A,满足1≤Ai≤i,每个数的正负号不知.请输出一种正负号的情况,使得所有数的和为0.(N≤100000) 解法:(我本来只想静静地继续做一个口胡选手...←_← 但是因为这 ...
-
UVA - 1614 Hell on the Market(贪心)
Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu Submit Status Descript ...
随机推荐
-
nodejs express template (模版)的使用 (ejs + express)
var app=require("express").createServer(); app.set("view engine","ejs" ...
-
使用Css截取字符串
white-space:nowrap; /* 禁止自动换行 */ overflow:hidden; /* 隐藏溢出的内容 */ text-overflow:ellipsis; /* 溢出文本使用... ...
-
JAVA_FastJson
package com.qf.mobiletrain01; import java.util.List; import com.alibaba.fastjson.JSON; class Student ...
-
Flume简介与使用(二)——Thrift Source采集数据
Flume简介与使用(二)——Thrift Source采集数据 继上一篇安装Flume后,本篇将介绍如何使用Thrift Source采集数据. Thrift是Google开发的用于跨语言RPC通信 ...
-
Windows Redis默认配置文件,Redis配置不生效解决方案
Windows Redis默认配置文件,Redis配置不生效解决方案, Windows Redis自启动配置不生效解决方案,Windows Redis增加自动启动服务 >>>> ...
-
关于java中反射的小结
一.Class 1. Class是一个类,封装了当前对象所对应的类的信息 2.小写class表示是一个类类型,大写Class表示这个类的名称 3.对于每个类而言,JRE 都为其保留一个不变的 Clas ...
-
luogu P3295 [SCOI2016]萌萌哒
传送门 题目条件"两个子串\(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 ...
-
python:3种爬虫的优缺点
性能对比 爬取方法 性 能 ...
-
一个python脚本解决安装mq的依赖问题
import tarfile import sys,os from _utils.patrol2 import run_cmd import zipfile def get_version(filen ...
-
0. 资料官网【从零开始学Spring Boot】
[视频&交流平台] àSpringBoot视频 http://study.163.com/course/introduction.htm?courseId=1004329008&utm ...