https://codeforces.com/contest/1130/problem/D1
이건데
6번째 테스트케이스에서 입력 이렇게 들어오거든
위 사진은 맨 초기 정거장마다 갖고있는 캔디 (인덱스 0부터 시작함 주의)
N=50 M=20 임
위 사진상에서 39 정거장 에서 출발했을때 질문드림
첫번쨰 싸이클은 어짜피 돌아야되니까 일단
answer += 50
해준다
캔디를 가장많이(2개) 갖고있는 정거장은 48이랑 2 정거장이니까 이 두개만 고려한다.
48정거장
두번째 싸이클때 49캔디를 픽해서 바로 다음정거장에 버리고 끝남 (첫번쨰 싸이클에서는 31캔디를 픽했었다고 가정)
이 경우 시간이 많이걸려봐야
출발정거장(39)에서 48까지 가는데 9, 그리고 바로 다음역에다 캔디 버리니까 1 더해서
9 + 1 = 10 이 나온다.
2정거장
두번째 사이클때 47캔디픽하면 30캔디에 비해 시간이 더 걸리니까 30캔디를 픽한다. (이경우 첫번째 싸이클에서 47픽했었다고 가정)
출발정거장(39) 에서 2까지 가는데 13, 그리고 2정거장에서 30정거장까지 가는데 28 더하면
13 + 28 = 41
즉 아무리 적게 걸려봐야
50 + 41 = 91 시간이 걸린다.
이게 내 풀이인데. 답은 93이라는데 어디서 잘못된걸까
5 3 1 2 1 3 5 4 하면 답 어떻게 나옴?
과연 캔디를 가장 많이 가지고 있는 것만 고려해야 할까? 만약 max-1개의 캔디를 가지고 있는데, 그 정거장이 시작 정거장의 바로 이전이고, 그 중 가장 가까운 정거장이 ㅈㄴ 멀다고 하면? 즉 정거장 2에서 시작을 하는데, 정거장 3에는 정거장 4로 가는 캔디가 2개 있고, 정거장 1에는 정거장 0으로 가는 캔디가 1개 있는 경우를 생각해보셈
아.. 그러네 38정거장에 32라는 복병이 이제 보이네
근데 이거 문제 만든사람은 이런거 다 예측하고 예제입력넣는거임? [캔디의 개수가 가장 많은 정거장만 고려하는새끼 반드시 하나 나온다] 하면서 내 풀이처럼 푸는애들 다 예측한다음 저렇게 반례를 집어넣는거? 너무 잔인하자너 ㅠㅠ
당연히 생각해서 반례 넣는데 아니어도 대부분 랜덤에서 걸러짐