贪心。

只考虑负数的位置，先填间隔较小的，再填间隔较大的。如果填不满就不填，如果有多余就留给最后一个负数到终点这段路。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int n,k,a[200010],sz;struct X{ int L,R,len;} s[200010];vector
             
              v;int f[200010];bool cmp(X a, X b){ return a.len
              
               k) printf("-1\n"); else { if(sum==0) printf("0\n"); else { for(int i=1; i<=n; i++) if(a[i]<0) v.push_back(i); for(int i=0; i
               
                =s[i].len) { for(int j=s[i].L;j<=s[i].R;j++) f[j]=1; sum=sum-s[i].len; } } if(sum>=n+1-v[v.size()-1]-1) { for(int i=v[v.size()-1];i<=n;i++) f[i]=1; } // for(int i=1;i<=n;i++) printf("%d ",f[i]); int ans=0; int f1=1,f2=n; for(int i=1;i<=n;i++) { if(f[i]==0) continue; else {f1=i;break;} } for(int i=n;i>=1;i--) { if(f[i]==0) continue; else {f2=i;break;} } ans=ans+1; if(f2!=n) ans=ans+1; for(int i=f1+1;i<=f2;i++) { if(f[i]!=f[i-1]) ans++; } printf("%d\n",ans); } } return 0;}