DAY5共2題：
儲(chǔ)物點(diǎn)的距離（前綴和）
糖糖別胡說(shuō)，我真的不是簽到題目（multiset，思維）
?? 作者：Eriktse
?? 簡(jiǎn)介：19歲，211計(jì)算機(jī)在讀，現(xiàn)役ACM銀牌選手??力爭(zhēng)以通俗易懂的方式講解算法！??歡迎關(guān)注我，一起交流C++/Python算法。（優(yōu)質(zhì)好文持續(xù)更新中……）??
?? 原文鏈接（閱讀原文獲得更好閱讀體驗(yàn)）：https://www.eriktse.com/algorithm/1096.html
儲(chǔ)物點(diǎn)的距離
題目鏈接：https://ac.nowcoder.com/acm/problem/14683
預(yù)處理出各點(diǎn)搬運(yùn)到點(diǎn)1和點(diǎn)n的代價(jià)前綴和，以及區(qū)間重量和。
假如我們要將區(qū)間[5, 7]的物品全部搬運(yùn)到3，代價(jià)應(yīng)該是區(qū)間[5, 7]的物品全部搬運(yùn)到的1，然后減去多搬的代價(jià)：[5, 7]的重量和 * dist(1, 3)。
上面是x < l的情況，x > r的情況類似。
當(dāng)l <= x <= r只需將區(qū)間[l, r]分為兩部分求和即可。
記得取模，距離要取模，前綴和也要取模。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9, p = 1e9 + 7;
//sum_l[i]表示區(qū)間[1, i]的物品都運(yùn)到點(diǎn)1的代價(jià)之和
//prefix_a[i]表示區(qū)間[1, i]的物品重量之和
//pos[i]是第i個(gè)點(diǎn)的位置，通過(guò)a[]作前綴和得到
int a[maxn], pos[maxn], sum_l[maxn], sum_r[maxn], prefix_a[maxn];
int n, m;
//取模函數(shù)
int mo(int x){return (x % p + p) % p;}
int f(int x, int l, int r)
{
if(l > r)return 0;
int res = 0;
if(x <= l)
{
res = mo(sum_l[r] - sum_l[l - 1]);
res = mo(res - mo(pos[x] - pos[1]) * mo(prefix_a[r] - prefix_a[l - 1]) % p);
}
else if(x >= r)
{
res = mo(sum_r[r] - sum_r[l - 1]);
res = mo(res - mo(pos[n] - pos[x]) * mo(prefix_a[r] - prefix_a[l - 1]) % p);
}
return res;
}
signed main()
{
scanf("%lld %lld",&n, &m);
pos[1] = 1;
for(int i = 2, d;i <= n; ++ i)scanf("%lld", &d), pos[i] = pos[i - 1] + d;
for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);
for(int i = 1;i <= n; ++ i)
{
sum_l[i] = mo(sum_l[i - 1] + a[i] * mo(pos[i] - pos[1]) % p);
sum_r[i] = mo(sum_r[i - 1] + a[i] * mo(pos[n] - pos[i]) % p);
}
for(int i = 1;i <= n; ++ i)prefix_a[i] = mo(prefix_a[i - 1] + a[i]);
while(m --)
{
int x, l, r;scanf("%lld %lld %lld", &x, &l, &r);
int ans = 0;
if(l <= x and x <= r)ans = mo(f(x, l, x - 1) + f(x, x + 1, r));
else ans = f(x, l, r);
printf("%lld\n", ans);
}
return 0;
}
糖糖別胡說(shuō)，我真的不是簽到題目
題目鏈接：https://ac.nowcoder.com/acm/problem/14583
本題有兩種解法，第一種容易理解，第二種效率更優(yōu)。
第一種解法：正向，multiset。
發(fā)功次數(shù)可以用一個(gè)桶來(lái)記錄，讓[1, i]的所有點(diǎn)的屬性值都+1，相當(dāng)于把后面的都-1，用一個(gè)fix表示偏移量。
建立兩個(gè)multiset表示兩組中的糖糖，好處是可以快速找出能力值最小的，從而去除掉。
掃一遍，把第i只糖糖加入到屬于它的集合中，然后將另外一個(gè)集合中已有的能力值小的糖糖進(jìn)行刪除，再檢查此時(shí)是否有發(fā)功。
最后集合中留下的糖糖個(gè)數(shù)即為答案。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9, inf = 8e18;
struct Node
{
int a, b;
}p[maxn];
int add[maxn];
void solve()
{
int n, m;scanf("%lld %lld",&n, &m);
memset(add, 0, sizeof(int) * (n + 2));
for(int i = 1;i <= n; ++ i)
scanf("%lld %lld", &p[i].a, &p[i].b);
//注意同一時(shí)間可能施法多次
for(int i = 1, x;i <= m; ++ i)scanf("%lld", &x), add[x] ++;
int fix = 0, cnt = 0;
multiset<int> st[2];
for(int i = 1;i <= n; ++ i)
{
int a = p[i].a, b = p[i].b - fix;
st[a].insert(b);
while(!st[a ^ 1].empty() and *st[a ^ 1].begin() < b)
st[a ^ 1].erase(st[a ^ 1].begin()), cnt ++;
fix += add[i];
}
printf("%lld\n", n - cnt);
}
signed main()
{
int _;scanf("%lld", &_);
while(_ --)solve();
return 0;
}
第二種解法：反向，思維。
我們想這么一個(gè)問(wèn)題，一個(gè)糖糖x是否會(huì)被刪除取決于在x出現(xiàn)之后，在另外一個(gè)集合中，是否出現(xiàn)了能力值高于x的能力值的糖糖y。
那么我們逆向遍歷，維護(hù)兩個(gè)集合的最值，當(dāng)前的新加入的糖糖x的能力值如果低于另外一個(gè)集合中已經(jīng)存在的（即右邊的）糖糖能力值的最大值，說(shuō)明他后面會(huì)被某個(gè)糖糖y刪除掉，直接打上標(biāo)記，但是我們不用真的刪除。
糖糖x還可以用于刪除左邊的另一個(gè)集合的能力值較小的糖糖。注意此時(shí)的發(fā)功應(yīng)該在循環(huán)開(kāi)始時(shí)進(jìn)行修改。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9, inf = 8e18;
struct Node
{
int a, b;
}p[maxn];
int add[maxn];
void solve()
{
int n, m;scanf("%lld %lld",&n, &m);
memset(add, 0, sizeof(int) * (n + 2));
for(int i = 1;i <= n; ++ i)
scanf("%lld %lld", &p[i].a, &p[i].b);
//注意同一時(shí)間可能施法多次
for(int i = 1, x;i <= m; ++ i)scanf("%lld", &x), add[x] ++;
int fix = 0, cnt = 0;
int mx[2] = {-inf, -inf};
for(int i = n;i >= 1; -- i)
{
fix += add[i];
int a = p[i].a, b = p[i].b + fix;
mx[a] = max(mx[a], b);
if(mx[a ^ 1] > b)cnt ++;
}
printf("%lld\n", n - cnt);
}
signed main()
{
int _;scanf("%lld", &_);
while(_ --)solve();
return 0;
}
?? 本文由eriktse原創(chuàng)，創(chuàng)作不易，如果對(duì)您有幫助，歡迎小伙伴們點(diǎn)贊??、收藏?、留言??
