正題

題目鏈接:https://www.luogu.com.cn/problem/AT3949

---

題目大意

長度為$L$的坐標軸上，給出$n$個點，每個點$x_i$需要購物$t_i$的時間，一輛車在$0～L$折返跑，求從$0$出發購物完回到$0$的最短時間。

$n\in [1,3\times 10^5],L\in [1,10^9]$，輸入的$x_i$單調遞增。

---

解題思路

挺奇妙的題目，$WC2021$講課的題。

首先每個$t_i$先$\%$上一個$2\times L$。然后把那些$2\times L$加到答案里先，這些無可避免。

然后考慮一個點，如果從右邊進只需要到達一次端點就視為左括號，如果從右邊進只需要到達一次端點就視為右括號。

先默認每個點的貢獻都是$2\times L$，顯然一個左括號和一個右括號匹配可以減少$2\times L$的貢獻，因為如果先走右邊那個再來走左邊那個，這樣他們的貢獻和就是$2\times L$。

而有些點既可以視為左又可以視為右，此時我們需要最大化匹配數。

其實還有一個性質，如果一個節點開始固定作為左括號，那么它后面的一定不會有固定作為右括號的（拿作為左右括號的條件看一下就能理解了）。所以不會有兩個固定的括號匹配。

然后就可以直接貪心匹配了，時間復雜度$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e5+10; int n,len,x[N],t[N],l[N],r[N],ans; int main() {scanf("%d%d",&n,&len);for(int i=1;i<=n;i++)scanf("%d",&x[i]);for(int i=1;i<=n;i++)scanf("%d",&t[i]);for(int i=1;i<=n;i++){ans+=t[i]/(2*len);t[i]%=2*len;if(!t[i]){ans--;continue;}l[i]=(t[i]<=x[i]*2);r[i]=(t[i]<=(len-x[i])*2);}int lim=n,L=0,R=0;ans+=n+1-r[n];for(int i=1;i<n;i++){if(!l[i]&&!r[i])continue;if(!r[i]){lim=i;break;}if(!l[i]&&L)L--,ans--;else if(l[i]) L++;}for(int i=n-1;i>=lim;i--){if(!l[i]&&!r[i])continue;if(!l[i])break;if(!r[i]&&R)R--,ans--;else if(r[i]) R++;}ans-=(L+R)>>1;printf("%lld\n",2ll*ans*len);return 0; }

總結

以上是生活随笔為你收集整理的AT3949-[AGC022D]Shopping【贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。