內容
給定一陣列 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;
}
|
