贪心算法求解划分最小平方和

    xiaoxiao2021-04-17  45

    #include<iostream> #include<math.h> #define max 100 using namespace std; bool tag[max]; void InitTag() { for(int i=0;i<max;i++) { tag[i]=false; } } int Tag(int k,int low,int high,int *s) { if(k==1) { return -1; } else { int average=(s[high]-s[low])/k; for(int i=low+1;i<=high;i++) { if((s[i]-s[low])>average) { if(abs(s[i]-s[low]-average)>abs(s[i-1]-s[low]-average)) { tag[i-1]=true; return i-1; } else { tag[i]=true; return i; } } } } } void Delete(int *a,int *s) { delete []a; delete []s; } void Print(int *a,int n) { for(int i=0;i<n;i++) { cout<<a[i]<<" "; if(tag[i+1]==true) { cout<<"|"; } } } void Print1(int *s,int n) { for(int i=0;i<=n;i++) { cout<<s[i]<<" "; } } int main() { int n,k; int *s,*a; cin>>n>>k; InitTag(); a=new int[n]; s=new int[n+1]; s[0]=0; int p=0; int m; for(int i=0;i<n;i++) { cin>>a[i]; p+=a[i]; s[i+1]=p; } int q=Tag(k,0,n,s); int count=k-1; while(q!=-1) { q=Tag(count,q,n,s); count--; } Print(a,n); Delete(a,s); return 0; } /* 9 4 1 2 3 4 5 6 7 8 9 */
    转载请注明原文地址: https://ju.6miu.com/read-674061.html

    最新回复(0)