The Walkway

問題建模

給定n個椅子，其中有m個位置存在商販，在商販處必須購買餅干吃，每隔經過d個椅子需要消耗餅干，在初始椅子1處也需要吃餅干，現在可以去除一個商販，問去除一個商販后所需消耗的餅干數量最小為多少，以及符合要求的商販數量。

問題分析

1.分析所求

題目需要輸出一個最小的餅干數量，以及對應符合要求的商販數量。則可以考慮采用枚舉計算每個商販缺失后所需的餅干數量，取數量最小的情況即可。

2.如何快速計算每個商販被去除后的餅干數量

由于到商販處必須買餅干，也就是到商販處計算椅子的間隔需要重新計算，則只需按商販間隔計算餅干數量即可。由于只去除一個商販，則可以預處理出所有商販都存在的餅干數量，然后計算出去除商販所需餅干數最少的情況即可。

代碼

#include<bits/stdc++.h>#define x first
#define y second
#define C(i) str[0][i]!=str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e5+10, INF = 0x3f3f3f3f;
int s[N];void solve() {int n,m,d;cin >>n >>m >>d;for(int i=1;i<=m;i++)   cin >>s[i];///計算方便計算第一個椅子和最后一個椅子到商販的間隔s[0]=1-d,s[m+1]=n+1;int ans=m;for(int i=0;i<=m;i++)   ans+=(s[i+1]-s[i]-1)/d;int val=0,cnt=0;///計算去除商販后減少餅干數量最多的for(int i=1;i<=m;i++){int a=s[i]-s[i-1]-1;int b=s[i+1]-s[i]-1;int c=s[i+1]-s[i-1]-1;if(val<a/d+b/d-c/d+1)   val=a/d+b/d-c/d+1,cnt=1;else if(val==a/d+b/d-c/d+1) cnt++;}cout <<ans-val <<" " <<cnt<<'\n';
}int main() {int t = 1;cin >> t;while (t--) solve();return 0;
}