018429's blog

By 018429, history, 3 years ago, In English

About the problem 1557B,what's the matter with following code , I can't figure out why it is always failed in case 58 of third test,I am almost crushed @^-^@

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
		int n,k;
		cin >> n >> k;
		vector<int> a(n),b(n);
		for(int i = 0;i < n;i++){
			cin >> a[i];
			b[i] = a[i]; 
		map<int,int> nxt;
		for(int i = 0;i < n - 1;i++)nxt[b[i]] = b[i+1];
		//nxt[b[n-1]] = b[n-1];
		int seg = 1;
		for(int i = 1;i < n;i++)if(a[i] != nxt[a[i-1]])seg++;
		if(seg <= k){
  	return 0;

OK,I just rewrite the code,and make a mistake again,when i make nxt[b[n-1] = b[n],I even pass 10th test,then I realize that the last number's next value will be value zero in map when I tempt to access by [].For Example,in the case n = 4,k = 1,arrays like: 3 0 1 2,the code will think this is non-decreasing,Finally,the problem is solved,so happy^_^

  • Vote: I like it
  • +1
  • Vote: I do not like it

3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a little suggestion, you can sort the indices of the array i (1,2,...,n) according to its corresponding value a[i] instead of maintaining a map. But both can be a good solution.