Test Message

e340: 差分練習

內容

給定一陣列 B,請輸出這個陣列的差分陣列 A。

定義 1 : 當 B[i]為 A[0]+A[1]+…A[i],B 陣列為 A 陣列的前綴和。

定義 2 : 當 B 陣列為 A 陣列的前綴和,A 陣列為 B 陣列的差分陣列。


輸入

輸入的第一行有一個整數 N (1 <= N <= 200000),代表 B 陣列大小。

第二行有 N 個整數以空白分隔,依序表示 B[0], B[1], B[2] … B[N-1]。

陣列中數字的絕對值不會超過 10^9。

5
1 2 3 4 5

輸出

輸出一行,其中有 N 個整數以空白分隔,依序表示 A[0], A[1], A[2] … A[N-1]。

1 1 1 1 1


解題思路

上一題差不多,改成用一個整數紀錄上一個元素,輸出當前元素減去上一個元素即可。

一樣不用做 IO 優化也能過。


完整程式碼

AC (23ms, 1.1MB)
#include <stdio.h>
#define BUFSIZ 1048576

inline char readChar()
{
static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
if (now == end)
{
if (end < buffer + BUFSIZ)
return EOF;
end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
now = buffer;
}
return *now++;
}

inline char readInt(int* dst)
{
register char ch;
while ((ch = readChar()) < '-')
if (ch == EOF) return 0;
if (ch == '-')
{
*dst = readChar() ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
*dst = ~*dst + 1;
}
else
{
*dst = ch ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
}
return 1;
}

inline void putInt(register int src, const char suffix)
{
register unsigned int div;
char buffer[13], * st = buffer + 11;
*st = suffix, * (st + 1) = 0;
if (src < 0)
{
src = ~src + 1;
*(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
while (src = div)
* (--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
*(--st) = '-';
}
else
{
do
{
*(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
} while (src = div);
}
fputs(st, stdout);
}

int main()
{
register int prev = 0;
long long tmp;
scanf("%*lld");
while (readInt(&tmp))
putInt((tmp - prev), ' '), prev = tmp;
return 0;
}