CCF CSP 202109-2 非零段划分【100分】

C++70分代码

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int arr[N],n;
int ss[N];
int judge(int num[], int n) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (num[i] != 0) {
            cnt++;
            while (num[i] != 0) i++;
        }
    }
    return cnt;
}
int maxn(int num[], int n) {
    int maxn = -1;
    for (int i = 0; i < n; i++) {
        if (num[i] > maxn) maxn = num[i];
    }
    return maxn;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int maxnn = maxn(arr, n);  //p的取值范围上限 
//    cout<<"maxnn ="<<maxnn<<endl; 
    int cnt = 0,geshu=0;
    for (int p = 1; p <= maxnn; p++) {
        for (int j = 0; j < n; j++) {
            if (arr[j] < p) ss[j] = 0;
            else ss[j] = arr[j];
        }
        geshu=judge(ss,n); //判断选取p后新数组ss的非零段个数 
        cnt=max(geshu,cnt); //将新数组非零段个数ss和之前得到的数组最大非零段个数比较 
    }
    cout << cnt;
    return 0;
}

Java70分代码

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
public class Main {
    static int[] a = new int[10000+5];
    static int[] temp = new int[10000+5];
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            set.add(a[i]);
        }
        Iterator<Integer> iterator = set.iterator();
        int max = 0;
        while (iterator.hasNext()){
            Integer p = iterator.next();
            for (int i = 1; i <= n; i++) {
                if(a[i]<p) temp[i] = 0;
                else temp[i] = a[i];
            }
            int fld = FLD(temp);
            max = Math.max(max,fld);
        }
        System.out.println(max);
    }

    private static int FLD(int[] temp) {
        int flag = 1,count = 0;
        for (int i = 1; i < temp.length; i++) {
            if(temp[i]!=0 && flag==1){
                count++;
                flag = 0;
            }
            if(temp[i]==0) flag = 1;
        }
        return count;
    }
}

C++70分 

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int A[500001];
int NZnum(int n){
	int NZ = 0;
	for(int i=1;i<=n;i++){
		if(A[i]>0 && A[i-1]==0) NZ++;
	}
	return NZ;
}
void PA(int p,int n){
	for(int i=1;i<=n;i++){
		if(A[i]<p) A[i] = 0;
	}
}
int main() {
	int n;
	int NZmax;
	A[0] = 0;
	cin>>n;
	set<int> s;
	for(int i=1;i<=n;i++){
		cin>>A[i];
		s.insert(A[i]);
	} 
	int temp = 0;
	NZmax = 0;
	int p;
	set<int>::iterator it1 = s.begin();
	while(it1!=s.end()){
		p = *it1;
		PA(p,n);
		temp = NZnum(n);
		if(NZmax<temp) NZmax = temp;
		++it1;
	}
	cout<<NZmax<<endl;
	return 0;
}

如何优化？1、空间换时间；2、处理逻辑的优化，如减少一些重复的操作，多利用一些历史的信息。

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int A[500002];
vector<int> pos[10001];

int main() {
	int n;
	A[0] = 0;
	cin>>n;
	set<int> s;
	for(int i=1;i<=n;i++){
		cin>>A[i];
		s.insert(A[i]);
		pos[A[i]].push_back(i);
	} 
	A[n+1] = 0;
	int NZ = 0;
	for(int i=1;i<=n;i++){
		if(A[i]>0 && A[i-1]==0) NZ++;
	}
	int temp;
	int NZmax;
	temp = NZmax = NZ;
	int p;
	set<int>::iterator it1 = s.begin();
	if(*it1==0) ++it1;
	while(it1!=s.end()){
		vector<int> &cp = pos[*it1];
		for(int i=0;i<cp.size();i++){
			int idx = cp[i];
			A[idx] = 0;
			if((A[idx-1]!=0)&&(A[idx+1]!=0)) temp++;
			if((A[idx-1]==0)&&(A[idx+1]==0)) temp--;	
		}
		++it1;
		NZmax = max(NZmax,temp);
	}
	cout<<NZmax<<endl;
	return 0;
}