2021-9-2非零段劃分（前綴和最簡(jiǎn)解法）（c/c++實(shí)測(cè)滿分）-創(chuàng)新互聯(lián)

總結(jié)

? 區(qū)間原地劃分時(shí)可以觀察相鄰元素之間的大小關(guān)系是否與劃分有關(guān)。前綴和與差分實(shí)現(xiàn)單位時(shí)間內(nèi)區(qū)間數(shù)值整體加1。（ccf-csp第二題真的很愛考前綴和。）

創(chuàng)新互聯(lián)從2013年開始，先為泊頭等服務(wù)建站，泊頭等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為泊頭企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

前綴和詳解：

一、題目要求

題目描述

A1,A2,?,An?是一個(gè)由?n?個(gè)自然數(shù)（非負(fù)整數(shù)）組成的數(shù)組。我們稱其中?Ai,?,Aj?是一個(gè)非零段，當(dāng)且僅當(dāng)以下條件同時(shí)滿足：

• 1≤i≤j≤n；
• 對(duì)于任意的整數(shù)?k，若?i≤k≤j，則?Ak>0；
• i=1?或?Ai?1=0；
• j=n?或?Aj+1=0。

下面展示了幾個(gè)簡(jiǎn)單的例子：

• A=[3,1,2,0,0,2,0,4,5,0,2]?中的?4?個(gè)非零段依次為?[3,1,2]、[2]、[4,5]?和?[2]；
• A=[2,3,1,4,5]?僅有?1?個(gè)非零段；
• A=[0,0,0]?則不含非零段（即非零段個(gè)數(shù)為?0）。

現(xiàn)在我們可以對(duì)數(shù)組?A?進(jìn)行如下操作：任選一個(gè)正整數(shù)?p，然后將?A?中所有小于?p?的數(shù)都變?yōu)?0。試選取一個(gè)合適的?p，使得數(shù)組?A?中的非零段個(gè)數(shù)達(dá)到大。若輸入的?A?所含非零段數(shù)已達(dá)大值，可取?p=1，即不對(duì)?A?做任何修改。

輸入格式

從標(biāo)準(zhǔn)輸入讀入數(shù)據(jù)。

輸入的第一行包含一個(gè)正整數(shù)?n。

輸入的第二行包含?n?個(gè)用空格分隔的自然數(shù)?A1,A2,?,An。

輸出格式

輸出到標(biāo)準(zhǔn)輸出。

僅輸出一個(gè)整數(shù)，表示對(duì)數(shù)組?A?進(jìn)行操作后，其非零段個(gè)數(shù)能達(dá)到的大值。

樣例1輸入

11
3 1 2 0 0 2 0 4 5 0 2

Data

樣例1輸出

5

二、我的解法（70）

#includeusing namespace std;

const int N=1e5;
int a[N],b[N];
bool st[N];//該值是否曾經(jīng)出現(xiàn)過

int main(){
	int n;
	cin>>n;
	int num=0;
	for(int i=0;ia[i-1]){//a[i-1]到a[i]-1段的p都能構(gòu)成新的非零段
			b[a[i]]--;//處理差分?jǐn)?shù)組以實(shí)現(xiàn)區(qū)間整體+1
			b[a[i-1]]++;
		}
	}

	int ans=0;
	for(int i=1;i<=M;i++){
		b[i]+=b[i-1];//求前綴和
		if(b[i]>ans) ans=b[i];//記錄前綴和數(shù)組中的大值
	}
	  
	cout<

分析：

? 當(dāng)a[i]>a[i-1]時(shí)，只要p取到區(qū)間a[i-1]到a[i]-1中的值，都能構(gòu)成一個(gè)新的非零段。這就是p與數(shù)組的關(guān)系，根據(jù)這個(gè)關(guān)系利用前綴和與差分實(shí)現(xiàn)單位時(shí)間內(nèi)區(qū)間數(shù)值整體加1，將雙重循環(huán)改進(jìn)至單層，降低計(jì)算時(shí)間。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：2021-9-2非零段劃分（前綴和最簡(jiǎn)解法）（c/c++實(shí)測(cè)滿分）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源：http://bm7419.com/article46/cdjseg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、網(wǎng)站收錄、ChatGPT、全網(wǎng)營(yíng)銷推廣、軟件開發(fā)、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)