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
亚洲国产精品无码久久SM
|
久久综合给久久狠狠97色
|
精品999久久久久久中文字幕
|
国产午夜福利精品久久2021
|
久久国产亚洲精品
|
一本色道久久综合亚洲精品
|
久久久久亚洲Av无码专
|
久久最新精品国产
|
伊人久久大香线蕉AV一区二区
|
无码人妻久久久一区二区三区
|
国产精品99精品久久免费
|
潮喷大喷水系列无码久久精品
|
国产香蕉97碰碰久久人人
|
精品久久久无码人妻中文字幕
|
韩国无遮挡三级久久
|
日韩美女18网站久久精品
|
久久综合给合久久狠狠狠97色69
|
中文字幕久久精品无码
|
久久国产色AV免费看
|
日本久久中文字幕
|
久久99国产精品二区不卡
|
东方aⅴ免费观看久久av
|
国产精品99久久久久久猫咪
|
亚洲人成伊人成综合网久久久
|
99久久精品免费看国产
|
99精品久久久久久久婷婷
|
久久强奷乱码老熟女网站
|
99久久久精品免费观看国产
|
伊人久久大香线蕉综合5g
|
国产免费福利体检区久久
|
久久99久久99小草精品免视看
|
中文国产成人精品久久不卡
|
亚洲αv久久久噜噜噜噜噜
|
国产视频久久
|
久久精品无码一区二区三区日韩
|
久久久久AV综合网成人
|
无码人妻久久一区二区三区蜜桃
|
久久精品成人免费看
|
久久亚洲精品国产精品
|
午夜久久久久久禁播电影
|
中文字幕久久波多野结衣av
|