時間復雜度
連續自然數和
對一個給定的正整數 $M$，求出所有的連續的正整數段（每一段至少有兩個數），這些連續的自然數段中的全部數之和為 $M$。
例子：$1998+1999+2000+2001+2002 = 10000$，所以從 $1998$ 到 $2002$ 的一個自然數段為 $M=10000$ 的一個解。
題目看到是連續數字相加，就可以用前綴和，可以化解為找兩點L和R， 使得sum[R] - sum[L - 1] 的和為 m。這里就可以從L=1到n開始便利，lower_bound函數找到滿足sum[L - 1] + m = sum[R]條件的下標,輸出即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int n, i, ix;
cin >> n;
vector<int> sum(n + 5);
sum[0] = 0;
for (i = 1; i <= n; i++)
sum[i] = sum[i - 1] + i;
for (i = 0; i < n; i++)
{
ix = lower_bound(sum.begin() + i + 1, sum.end(), n + sum[i]) - sum.begin();
if (sum[ix] == sum[i] + n && ix - (i + 1) + 1 > 1)
{
cout << i + 1 << " " << ix << endl;
}
}
}
數列分段 Section II
對于給定的一個長度為 $N$ 的正整數數列 $A_{1\sim N}$，現要將其分成 $M$（$M\leq N$）段，并要求每段連續，且每段和的最大值最小。
關于最大值最小：
例如一數列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。
將其如下分段：
$$[4\ 2][4\ 5][1]$$
第一段和為 $6$，第 $2$ 段和為 $9$，第 $3$ 段和為 $1$，和最大值為 $9$。
將其如下分段：
$$[4][2\ 4][5\ 1]$$
第一段和為 $4$，第 $2$ 段和為 $6$，第 $3$ 段和為 $6$，和最大值為 $6$。
并且無論如何分段，最大值不會小于 $6$。
所以可以得到要將數列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小為 $6$。
解：
對于求最大值的最小值的問題是典型的二分問題，無法找出直接解決問題的思路，使用二分，以O(log2n)的速度找出答案 (在[0, 1e5]的范圍內，精確到1e-8只需要44次)
這道題二分最大和的最小值，最大和設為x, 范圍在[max of array, sum of array]中，規定了劃分為m個區間，對于 x 較小的，會使得劃分的區間數比m大， x較大的劃分的區間數會比m小， 通過合理二分我們能找到合法且最小的區間。
(為了尋找x的最小合法值，二分向答案靠近，設check()函數的條件為 num <= k 即當前區間數較小或相等時，在二分時x選的過大或是在滿足條件的一個值[不一定為最大值的最小值]將右邊界縮小，而選取x過小時，left = mid + 1 說明最后二分結果一定在left = mid + 1 = right 這個情況是在x選取過小到x剛好合法的時候，即最后答案要求的最小滿足的答案。由此我們也可以推出當改變條件邊界，也可求出題目要求的最大值，改變check(num >= m), left = mid, right = mid - 1)
二分想好了，其實劃分區間也很簡單，就是通過貪心，盡量將能放在一起的放在一起。
在遍歷整個數組的過程中，累加當前區間的總和sum，若此時加入a[i]后，sum + a[i] > x,這說明區間已滿，需要再新開一個區間，每次新開記錄數量，即得當前x的區間數num。
二分條件：
- 當分段數num > m時，指定最大值太小， left = mid + 1
- 當分段數num = m時，指定分段數合法，繼續向左邊看有無更小的，保留當前邊界
- 當分段數num < m時, 指定最大值太大， right = mid；
int check(int x)
{
int sum = 0, num = 1;
for (int i = 1; i <= n; i++)
{
if (sum + a[i] <= x)
sum += a[i];
else
{
sum = a[i];
num++;
}
}
return num <= m;
}
while (left < right)
{
mid = (left + right) >> 1;
if (check(mid))
{
right = mid;
}
else
left = mid + 1;
}
完整代碼
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], n, k;
bool check(int x)
{
int duan = 0, now = 0;
for (int i = 1; i <= n; i++)
{
if (now + a[i] <= x)
{
now += a[i];
}
else
{
now = a[i];
duan++;
if (duan > k)
return 0;
}
}
if (now)
duan++;
return duan <= k;
}
int main()
{
int left, right, mid, maxx = 0, sum = 0;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
maxx = max(a[i], maxx);
sum += a[i];
}
left = maxx;
right = sum;
while (left < right)
{
mid = (left + right) >> 1;
if (check(mid))
{
right = mid;
}
else
left = mid + 1;
}
cout << right << endl;
}
你可能會問 如果x選的值是使得num合法的判斷，但是沒有一個區間達到了最大值，但其實此時達到合法值了，但是為了找到更小的會向左尋找更小的x，直到此時x滿足某個區間為最大值。
抽象出最大值最小化，最小值最大化的模型：
找出二分范圍， 用check條件判斷，提前找出題目限制條件。
通往奧格瑞瑪的道路
題目背景
在艾澤拉斯大陸上有一位名叫歪嘴哦的神奇術士，他是部落的中堅力量。
有一天他醒來后發現自己居然到了聯盟的主城暴風城。
在被眾多聯盟的士兵攻擊后，他決定逃回自己的家鄉奧格瑞瑪。
題目描述
在艾澤拉斯，有 $n$ 個城市。編號為 $1,2,3,\ldots,n$。
城市之間有 $m$ 條雙向的公路，連接著兩個城市，從某個城市到另一個城市，會遭到聯盟的攻擊，進而損失一定的血量。
每次經過一個城市，都會被收取一定的過路費（包括起點和終點）。路上并沒有收費站。
假設 $1$ 為暴風城，$n$ 為奧格瑞瑪，而他的血量最多為 $b$，出發時他的血量是滿的。如果他的血量降低至負數，則他就無法到達奧格瑞瑪。
歪嘴哦不希望花很多錢，他想知道，在可以到達奧格瑞瑪的情況下，他所經過的所有城市中最多的一次收取的費用的最小值是多少。
輸入格式
第一行 $3$ 個正整數，$n,m,b$。分別表示有 $n$ 個城市，$m$ 條公路，歪嘴哦的血量為 $b$。
接下來有 $n$ 行，每行 $1$ 個正整數，$f_i$。表示經過城市 $i$，需要交費 $f_i$ 元。
再接下來有 $m$ 行，每行 $3$ 個正整數，$a_i,b_i,c_i$（$1\leq a_i,b_i\leq n$）。表示城市 $a_i$ 和城市 $b_i$ 之間有一條公路，如果從城市 $a_i$ 到城市 $b_i$，或者從城市 $b_i$ 到城市 $a_i$，會損失 $c_i$ 的血量。
輸出格式
僅一個整數，表示歪嘴哦交費最多的一次的最小值。
如果他無法到達奧格瑞瑪，輸出 AFK。
//大TLE TLE TLE
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 5;
pair<int, int> f[N];
int a[N][N], dis[N], vis[N];
int n, m, b;
bool check(int x)
{
// cout << "!11" << endl;
int i, j, xx;
vector<int> aa;
for (i = 1; i <= x; i++)
aa.push_back(f[i].first);
for (i = 1; i <= n; i++)
dis[i] = 1e18;
memset(vis, 0, sizeof(vis));
dis[1] = 0;
int ff, minn;
while (1)
{
minn = 0x3f;
ff = -1;
for (auto pos = aa.begin(); pos != aa.end(); ++pos)
{
xx = *pos;
if (!vis[xx] && minn > dis[xx])
{
ff = xx;
minn = dis[xx];
}
}
if (ff == -1)
break;
vis[ff] = 1;
for (auto pos = aa.begin(); pos != aa.end(); ++pos)
{
i = *pos;
if (a[i][ff] != 0)
dis[i] = min(dis[i], dis[ff] + a[i][ff]);
}
}
cout << dis[n] << endl;
if (dis[n] <= b)
return true;
return false;
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
if (a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int i, x, y, ss, j;
cin >> n >> m >> b;
for (i = 1; i <= n; i++)
{
cin >> f[i].second;
f[i].first = i;
}
for (i = 1; i <= n; i++)
{
for (j = 1; j <= i; j++)
{
a[i][j] = 1e9;
a[j][i] = 1e9;
}
}
int f1 = max(f[1].second, f[n].second);
for (i = 0; i < m; i++)
{
cin >> x >> y >> ss;
a[x][y] = ss;
a[y][x] = ss;
}
sort(f + 1, f + 1 + n, cmp);
int left = 1, right = n, mid;
while (left < right)
{
mid = (left + right) >> 1;
if (check(mid))
{
right = mid;
}
else
{
left = mid + 1;
}
}
if (!check(right))
cout << "AFK" << endl;
else
{
cout << f[right].second << endl;
}
}
解：
將最大值收入的最小值進行二分，check()函數內使用dijkstra算最短路徑，注意最短路徑時，要考慮路徑的存儲，用鏈式前向星來存，矩陣數組空間冗余過多會報錯，在while循環內找當前最短dis時，也需要用到更優化的結構，把從1到每一個點的最短路徑dis[n]用小根堆 + pair的形式存，即優先隊列 priority_queue
compare: 鏈式前向星的存儲方式完全適配于dijkstra的算法，在尋找到最小的dis[n]時，重新更新所有未進隊的節點dis值，直接便利head即可，存取都十分方便，還有就是時間復雜度上面，沒有必要每一次check()都進行一次預處理把可以走的節點拉出來，直接在dijkstra更新的時候直接加上判斷條件，收費值大于x的直接不更新，也不會進隊，直接屏蔽。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 5;
const int M = 1e5 + 5;
int n, m, b, f[N], vis[N], dis[N];
int cnt = 0, head[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
struct edge
{
int to, next, s;
} ed[M];
void add(int xx, int yy, int ss)
{
ed[++cnt].to = yy;
ed[cnt].next = head[xx];
head[xx] = cnt;
ed[cnt].s = ss;
}
bool check(int x)
{
int ddis, index, i, yy, cost;
memset(vis, 0, sizeof(vis));
for (i = 1; i <= n; i++)
dis[i] = 1e9;
if (f[1] > x || f[n] > x)
return 0;
dis[1] = 0;
que.push({0, 1});
while (!que.empty())
{
index = que.top().second;
ddis = que.top().first;
que.pop();
if (vis[index])
continue;
vis[index] = 1;
for (i = head[index]; i != -1; i = ed[i].next)
{
yy = ed[i].to;
cost = ed[i].s;
if (f[yy] <= x && !vis[yy] && dis[yy] > ddis + cost)
{
dis[yy] = ddis + cost;
que.push({dis[yy], yy});
}
}
}
if (dis[n] <= b)
return 1;
return 0;
}
signed main()
{
int i, xx, yy, ss, maxx = 0, minn = 1e9 + 10;
cin >> n >> m >> b;
for (i = 0; i < n; i++)
{
cin >> f[i + 1];
maxx = max(maxx, f[i + 1]);
minn = min(minn, f[i + 1]);
}
memset(head, -1, sizeof(head));
for (i = 0; i < m; i++)
{
cin >> xx >> yy >> ss;
add(xx, yy, ss);
add(yy, xx, ss);
}
int left = minn, right = maxx, mid;
while (left < right)
{
mid = (left + right) >> 1;
if (check(mid))
{
right = mid;
}
else
{
left = mid + 1;
}
}
if (!check(maxx))
{
cout << "AFK" << endl;
}
else
{
cout << left << endl;
}
}
后置知識
鏈式前向星+小根堆dijstra
小根堆定義
//隊列內類型，容器，排列方式（仿函數）
priority_queue<pair<int, int>, vector<int, int>, greater<pair<int, int>>>;
鏈式前向星定義：
struct edge
{
int to, next, len;
} e[M];
添加邊：
void add(int x, int y, int z)
{
e[++t].len = z;
e[t].to = y;
e[t].next = head[x];
head[x] = t;
}
便利方式：
s2 = head[ff];
while (s2 != -1)
{
}
進擊的奶牛
題目描述
Farmer John 建造了一個有 $N$（$2 \leq N \leq 10 ^ 5$) 個隔間的牛棚，這些隔間分布在一條直線上，坐標是 $x _ 1, x _ 2, \cdots, x _ N$（$0 \leq x _ i \leq 10 ^ 9$）。
他的 $C$（$2 \leq C \leq N$）頭牛不滿于隔間的位置分布，它們為牛棚里其他的牛的存在而憤怒。為了防止牛之間的互相打斗，Farmer John 想把這些牛安置在指定的隔間，所有牛中相鄰兩頭的最近距離越大越好。那么，這個最大的最小最近距離是多少呢？
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, c, pos[N];
bool check(int x)
{
int now = 0, num = 1;
for (int i = 1; i < n; i++)
{
if (now < x)
{
now += pos[i + 1] - pos[i];
}
else
{
num++;
now = pos[i + 1] - pos[i];
}
}
if (now >= x)
num++;
return num >= c;
}
signed main()
{
int i;
cin >> n >> c;
for (i = 1; i <= n; i++)
cin >> pos[i];
sort(pos + 1, pos + n + 1);
int minn = 1e18, maxx = pos[n] - pos[1];
for (i = 1; i < n; i++)
{
minn = min(minn, pos[i + 1] - pos[i]);
}
int left = minn, right = maxx, mid;
while (left < right)
{
mid = (left + right + 1) / 2;
if (check(mid))
left = mid;
else
right = mid - 1;
}
cout << left << endl;
}
解：二分求相鄰奶牛最小距離的最大值，板刷題目。二分距離范圍在[最小的間距，第一個牛棚到最后一個的距離]。
浙公網安備 33010602011771號