我觉得第二题要剪枝,比如k=1,你[1,2,3,3,4]的话i从1开始到3为止,i=2的时候就要可以从4开始,中间的上一次计算过了,只需加一下,没考试,上一下自己的程序,不知道对不对

int main() { int n, k;
  cin >> n >> k; int v[n]; for(int i=0; i<n; ++i) {
    cin >> v[i];
  } int last = 0; int result = n;//最少有4个  for(int start = 0; start < n - 1; ++start) { int cnt = 1; int record[10];//record[i+1]表示i出现的次数,0-9  memset(record, 0, sizeof(record)); for(int i = start; i <= last; ++i) { if(record[v[i] + 1]==0)
        record[v[i] + 1] = 1;//初始只出现了一次  else  ++record[v[i] + 1];
    }
    result += (last - start); for(int end = last + 1; end < n; ++end) {
      record[v[end]+1]++; if(record[v[end]+1] > k) {//重复次数超过k  last = end - 1;//下一次从last+1开始,因为下一次到last也都可以  break;
      } else if(end < n - 1) {
        ++result;
      } else { if(record[v[end]+1] <= k)
          ++result;
        last = end;//到达最后一个了  }
    }
  }

  cout<<result<<endl;

}

创作者周榜