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
閱讀(171)
評論(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
@楊書鑒
你寫的排序好像不對啊。。。
--小猊
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 _Yuan
91久久精品国产91性色也
|
久久久久亚洲?V成人无码
|
日日噜噜夜夜狠狠久久丁香五月
|
久久99精品国产麻豆宅宅
|
97香蕉久久夜色精品国产
|
亚洲国产精品无码久久一线
|
国产韩国精品一区二区三区久久
|
国产精品一久久香蕉产线看
|
国内精品久久久久国产盗摄
|
久久久精品久久久久影院
|
91久久精品91久久性色
|
久久久久18
|
久久久久99精品成人片直播
|
99久久国产综合精品五月天喷水
|
亚洲天堂久久久
|
久久精品www
|
亚洲综合伊人久久大杳蕉
|
精品久久久无码中文字幕天天
|
久久精品国产色蜜蜜麻豆
|
久久精品a亚洲国产v高清不卡
|
久久精品夜色噜噜亚洲A∨
|
日韩乱码人妻无码中文字幕久久
|
国产精品成人久久久久久久
|
久久久久久久久波多野高潮
|
狠狠色丁香婷婷综合久久来来去
|
99久久免费国产精品热
|
亚洲国产成人久久一区WWW
|
国产激情久久久久影院老熟女
|
欧美伊人久久大香线蕉综合
|
精品无码久久久久久国产
|
久久国产一区二区
|
久久91综合国产91久久精品
|
精品综合久久久久久97
|
久久久午夜精品
|
久久精品一本到99热免费
|
亚洲人成电影网站久久
|
亚洲精品视频久久久
|
欧美亚洲国产精品久久久久
|
久久人人爽人爽人人爽av
|
国产精品久久永久免费
|
久久亚洲中文字幕精品有坂深雪
|