Yuan
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
CII 4378 构造法 不会证明 ★★★
/**/
/*
题意:给出a[i] 现在要求使得∑ai*bi = 0 bi = -1,1 其中1<=ai<=i
n <= 10^5
若没有 1<=ai<=i 可用dp做,但数据规模太大了
标程是用贪心,从后往前贪
不断使答案sum趋近于0
*/
#include
<
cstdio
>
#include
<
cstring
>
const
int
MAXN
=
100010
;
int
a[MAXN],f[MAXN];
int
main()
{
int
N;
while
(
~
scanf(
"
%d
"
,
&
N) )
{
for
(
int
i
=
1
; i
<=
N; i
++
)
scanf(
"
%d
"
,
&
a[i]);
int
sum
=
0
;
for
(
int
i
=
N; i ; i
--
)
{
if
(sum
<=
0
) sum
+=
a[i] , f[i]
=
1
;
else
sum
-=
a[i], f[i]
=
-
1
;
}
if
(sum)puts(
"
No
"
);
else
{
puts(
"
Yes
"
);
for
(
int
i
=
1
; i
<=
N ; i
++
)
{
if
(i
>
1
)putchar(
'
'
);
printf(
"
%d
"
,f[i]);
}
}
}
return
0
;
}
发表于 2010-10-05 17:49
_Yuan
阅读(168)
评论(0)
编辑
收藏
引用
所属分类:
OJ解题报告
常用链接
我的随笔
我的评论
我参与的随笔
随笔分类
Dp(27)
(rss)
OJ解题报告(153)
(rss)
OThers(17)
(rss)
TopCoder
(rss)
计算几何(2)
(rss)
枚举(4)
(rss)
数据结构(6)
(rss)
数论(5)
(rss)
搜索(2)
(rss)
贪心(4)
(rss)
图论(10)
(rss)
学习笔记(6)
(rss)
学习总结(19)
(rss)
组合数学(3)
(rss)
Links
Lord Li
Lord zeus
搜索
最新评论
1. re: 双向BFS[未登录]
博主,只用一个队列不就可以解决你第一个问题了吗
--jason
2. re:nvgagkguaioguaiiananfajfofajiosfgoasoajgia[未登录]
cscdcuis
--1
3. re: zoj 3436 逆推 搜
评论内容较长,点击标题查看
--ZH
4. re: zoj 2318 计算几何 spfa判负环
写得好!
--ipqhjjybj
5. re: Poj 1066
@杨书鉴
你写的排序好像不对啊。。。
--小猊