Yuan
|
首頁
|
發(fā)新隨筆
|
發(fā)新文章
|
聯(lián)系
|
聚合
|
管理
CII 4378 構(gòu)造法 不會(huì)證明 ★★★
/**/
/*
題意:給出a[i] 現(xiàn)在要求使得∑ai*bi = 0 bi = -1,1 其中1<=ai<=i
n <= 10^5
若沒有 1<=ai<=i 可用dp做,但數(shù)據(jù)規(guī)模太大了
標(biāo)程是用貪心,從后往前貪
不斷使答案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
;
}
發(fā)表于 2010-10-05 17:49
_Yuan
閱讀(178)
評(píng)論(0)
編輯
收藏
引用
所屬分類:
OJ解題報(bào)告
常用鏈接
我的隨筆
我的評(píng)論
我參與的隨筆
隨筆分類
Dp(27)
(rss)
OJ解題報(bào)告(153)
(rss)
OThers(17)
(rss)
TopCoder
(rss)
計(jì)算幾何(2)
(rss)
枚舉(4)
(rss)
數(shù)據(jù)結(jié)構(gòu)(6)
(rss)
數(shù)論(5)
(rss)
搜索(2)
(rss)
貪心(4)
(rss)
圖論(10)
(rss)
學(xué)習(xí)筆記(6)
(rss)
學(xué)習(xí)總結(jié)(19)
(rss)
組合數(shù)學(xué)(3)
(rss)
Links
Lord Li
Lord zeus
搜索
最新評(píng)論
1.?re: 雙向BFS[未登錄]
博主,只用一個(gè)隊(duì)列不就可以解決你第一個(gè)問題了嗎
--jason
2.?re:nvgagkguaioguaiiananfajfofajiosfgoasoajgia[未登錄]
cscdcuis
--1
3.?re: zoj 3436 逆推 搜
評(píng)論內(nèi)容較長,點(diǎn)擊標(biāo)題查看
--ZH
4.?re: zoj 2318 計(jì)算幾何 spfa判負(fù)環(huán)
寫得好!
--ipqhjjybj
5.?re: Poj 1066
@楊書鑒
你寫的排序好像不對(duì)啊。。。
--小猊
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 _Yuan
国产精品99精品久久免费
|
国产精品久久久久久吹潮
|
久久青青草原精品国产不卡
|
久久久久久狠狠丁香
|
日韩一区二区三区视频久久
|
久久AV无码精品人妻糸列
|
亚洲国产成人久久精品影视
|
无码任你躁久久久久久久
|
乱亲女H秽乱长久久久
|
99久久婷婷国产综合精品草原
|
四虎国产精品成人免费久久
|
狠狠色丁香婷婷综合久久来
|
亚洲欧美一区二区三区久久
|
99国内精品久久久久久久
|
亚洲AV无码久久精品色欲
|
精品久久人人爽天天玩人人妻
|
天堂久久天堂AV色综合
|
思思久久99热免费精品6
|
国产精品久久久久久影院
|
久久人与动人物a级毛片
|
久久久久国色AV免费看图片
|
久久99热狠狠色精品一区
|
午夜精品久久久久久中宇
|
三级韩国一区久久二区综合
|
97久久精品人人做人人爽
|
国产99精品久久
|
精品熟女少妇a∨免费久久
|
无码精品久久久天天影视
|
亚洲AV无码一区东京热久久
|
久久天天躁夜夜躁狠狠躁2022
|
久久丝袜精品中文字幕
|
久久国产热这里只有精品
|
国产一区二区精品久久凹凸
|
国产精品青草久久久久福利99
|
久久精品国产精品青草app
|
久久精品国产清高在天天线
|
久久久婷婷五月亚洲97号色
|
蜜臀av性久久久久蜜臀aⅴ
|
久久精品国产亚洲AV电影
|
欧洲精品久久久av无码电影
|
久久综合给合久久国产免费
|