大家好,今天是2021年的第一天,讓我們鼓足幹勁大幹一場。今天我們選擇的依然是字節跳動2019年的筆試題,題目來源於牛客網。
這道題難度同樣不是很大,但是非常考驗基礎,基礎稍稍不夠紮實的同學很有可能寫出了算法,但是依然會陷入各種問題當中無法AC。我個人覺得差不多是LeetCode Medium水平的難度,但是需要大家有點耐心,開動腦筋反覆思考。
題目連結:https://www.nowcoder.com/question/next?pid=16516564&qid=362293&tid=40247384
好了,我們不多說廢話,直接來看題吧。
我叫王大錘,是一名特工。我剛剛接到任務:在字節跳動大街進行埋伏,抓捕恐怖分子孔連順。和我一起行動的還有另外兩名特工,我提議
為了相互照應,我們決定相距最遠的兩名特工間的距離不超過D。
我特喵是個天才! 經過精密的計算,我們從X種可行的埋伏方案中選擇了一種。這個方案萬無一失,顫抖吧,孔連順!
……
萬萬沒想到,計劃還是失敗了,孔連順化妝成小龍女,混在cosplay的隊伍中逃出了字節跳動大街。只怪他的偽裝太成功了,就是楊過本人來了也發現不了的!
請聽題:給定N(可選作為埋伏點的建築物數)、D(相距最遠的兩名特工間的距離的最大值)以及可選建築的坐標,計算在這次行動中,大錘的小隊有多少種埋伏選擇。
注意:
三個特工是等價的:即同樣的位置組合(A, B, C) 只算一種埋伏方法,不能因「特工之間互換位置」而重複使用
輸入描述:第一行包含空格分隔的兩個數字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)
第二行包含N個建築物的的位置,每個位置用一個整數(取值區間為[0, 1000000])表示,從小到大排列(將字節跳動大街看做一條數軸)
輸出描述:一個數字,表示不同埋伏方案的數量。結果可能溢出,請對 99997867 取模
輸入例子1:4 3
1 2 3 4
輸出例子1:4
例子說明1:可選方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)
輸入例子2:5 19
1 10 20 30 50
輸出例子2:1
例子說明2:可選方案 (1, 10, 20)
題解
首先我們來理一下題目當中出現的幾個點,我們要算的是特工埋伏的方法數。特工埋伏需要固定3個特工,並且要求特工之間的距離小於D。
題目當中還說特工之間是等價的,如果大家敏感的話,這其實是一道排列組合問題,準確的說是一道組合問題。這和n球裡任意取3個出來有多少種組合本質上是一樣的,如果大家還記得組合公式的話套一下就可以了:
這裡的k固定了是3,我們代入進去可以簡化為:
首先,由於題目當中說的是特工分布在一條大街上,我們可以把大街看成是橫坐標軸,每一個特工就是坐標軸上的一個點。由於題目當中限定了3個特工之間的距離不超過D,其實也就是最左側和最右側的距離小於D。我們可以想像有一個長度為D的線段在這個坐標軸上滑動,窗口內的特工數量就是n。
由於特工的位置是固定的,所以這個n是很好算的。假如我們用一個數組sum來存儲從0開始到當前位置一共包含的特工數,那麼區間[x, x+D]範圍內的特工數量其實就等於sum[x+D]-sum[x]。這裡我們可以通過差分數組來搞定,也可以使用樹狀數組,我這裡用了樹狀數組,其實沒有必要,因為不涉及更新操作。
所以接下來我們要做的就是把這個窗口從最左側往右滑動就可以了,每次窗口內特工變化的時候,我們計算一下構成的組合數累加在一起就可以了。進一步我們可以想到,其實我們只需要關心窗口的左邊緣,我們把窗口的左邊緣和特工重疊,這樣能夠使得窗口內的特工數量儘可能多。
比如[1, 2, 3, 4]這個樣例,顯然當窗口的左邊緣和1重疊的時候,能夠把4也覆蓋了,否則就會遺漏一些情況。很多人想到這裡就去寫代碼了,但是這裡藏了一個trick,當我們的窗口移動的時候,實際上會出現有一些組合重複的情況。
比如說窗口長度是4,當前窗口內的特工是[1, 2, 3, 4],其中有一種組合是(2, 3, 4)。當我們窗口左側邊緣移動到2的時候,窗口內的特工是[2, 3, 4, 5],這裡同樣可以構成組合(2, 3, 4),這就構成了重複,我們需要去掉這一種方案。去的方法也很簡單,我們每次移動窗口的時候都記錄下移動之前的窗口右邊緣的位置。當我們移動之後,我們當前左側邊緣和上次右側邊緣中的特工是重複的,我們需要去掉相關情況。
比如說,我們移動之前是[1, 5, 6, 7],移動之後是[5, 6, 7, 8, 10, 12]。當前的左側邊緣是5,上次的右側邊緣是7,[5, 7]這個區間內的組合數就是重複的情況, 我們需要去掉。另外我們還需要注意一下邊界的事情,由於我們計算組合數需要用到三方的計算,而n最大是1e6,三次方之後就是1e18的範圍,顯然使用int是扛不住的,必須要用long long, long long的範圍是2e18,基本上注意這幾點就可以AC了。
最後,我們來看代碼。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
#define pii pair<int, int>
using namespace std;
const int N=1000050;
const long long Mod=99997867;
int x, y;
int arr[N];
// 樹狀數組
int lowbit(int x) {
return x & (-x);
}
void update(int x, int y) {
for (int i = x; i < N; i += lowbit(i)) {
arr[i] += y;
}
}
int query(int x) {
int ret = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
ret += arr[i];
}
return ret;
}
long long cal(long long x) {
return x * (x-1) * (x-2) / (long long) 6;
}
int main() {
int n, d;
scanf("%d%d", &n, &d);
vector<int> positions;
rep(i, 0, n) {
int u;
scanf("%d", &u);
u += 1;
positions.push_back(u);
update(u, 1);
}
long long ret = 0;
int last = 0;
for (int i = 0; i < positions.size(); i++) {
int u = positions[i];
long long num = query(u+d) - query(u-1);
if (num < 3) continue;
long long cur = cal(num);
// 去掉重複的可能性
if (last > u) {
long long cnum = query(last) - query(u-1);
cur -= cal(cnum);
}
ret = ((ret + cur) % Mod + Mod) % Mod;
last = u + d;
}
printf("%lld\n", ret);
return 0;
}代碼裡有一個細節,我們在對最終結果進行取模的時候,不是直接% Mod,而是用了一個比較複雜的方式:ret = ((ret + cur) % Mod + Mod) % Mod;。這是因為我們直接取模在一些情況下可能會得到負數,會影響我們的結果,所以需要通過這種方式來確保得到的結果一定是正數。
今天的文章就到這裡,衷心祝願大家每天都有所收穫。如果還喜歡今天的內容的話,請來一個三連支持吧~(點讚、在看、轉發)