Codeforces Beta Round #11

点击打开链接

A

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 2010;
int n , d;
int num[MAXN];

int main(){
    while(scanf("%d%d" , &n , &d) != EOF){
        for(int i = 0 ; i < n ; i++)
           scanf("%d" , &num[i]);
        int ans = 0;
        for(int i = 1 ; i < n ; i++){
            if(num[i] == num[i-1]){
               num[i] += d;
               ans++;
            }
            else if(num[i] < num[i-1]){
               int tmp = num[i-1]-num[i];
               ans += tmp/d + 1;
               num[i] += (tmp/d+1)*d;//这个地方注意一下
            }
        }
        printf("%d\n" , ans);
    }
    return 0;
}

B

思路：找规律
分析：
1 首先我们应该知道当n为负数的时候情况和正数是一样的，所以一律按照正数处理
2 考虑特殊的情况，当n = 0 和 n = 1的时候我们应该输出n即可。当n >= 2的时候我们就要开始找规律，题目说每一步可以向左也向右，那么我们把向右看成是正数，向左看成是负数。
第一：找到1+2+3+...+x  = sum >= n，假设刚好sum = n，那么ans就是x，否则进行第二
第二：找到差值tmp = sum-n，如果tmp是偶数那么肯定可以1,2,3...x中改变某一个数a为负数使得和变为sum-2a = n，如果不是偶数进行第三
第三：对tmp进行累加，从x+1,x+2...，加到刚刚使得tmp为偶数即可

3 举例说明 n=7：
第一：找到1+2+3+4 = 10 > 7
第二：找到差值tmp = 3 不是偶数
第三：tmp+5 = 8是偶数，那么变成1+2+3+4+5 = 15 > 7 ,差值为8，那么最后的序列为1+2+3-4+5 = 7，这样就可以找到是怎么从0到7的“先向右跳3次，然后向左，最后向右到7”

4 为什么上面的找规律的方法是对的呢？
假设数轴上面-5  -4  -3  -2  -1  0  1  2  3  4  5 ， 那么0-5的位移量是5，那么我们设向左是负数向右是正数。
根据位移可知可以找到一个等式1+2+3+4-5 = 0，就是向右1，向右2，向右3，向右4，向左5就到5这个点。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n , ans;
    while(scanf("%d" , &n) != EOF){
        n = abs(n);
        if(!n || n == 1){
          printf("%d\n" , n);
          continue;
        }
        int sum = 0;
        int mark;
        for(int i = 1 ; ; i++){
           sum += i;
           if(sum >= n){
              mark = i;
              break;
           }
        }
        int tmp = sum-n;
        if(tmp%2){
           while(1){
              tmp += mark+1;
              mark++;
              if(tmp%2 == 0)
                 break;
           }
        }
        printf("%d\n" , mark);
    }
    return 0;
}