网页设计作业怎么做网站,wordpress内存分配不足,wordpress注册邮箱空白,免费代理加盟好项目文章目录 [The Walkway](https://codeforces.com/contest/1858/problem/B)问题建模问题分析1.分析所求2.如何快速计算每个商贩被去除后的饼干数量代码 The Walkway 问题建模
给定n个椅子#xff0c;其中有m个位置存在商贩#xff0c;在商贩处必须购买饼干吃#xff0c;每隔… 文章目录 [The Walkway](https://codeforces.com/contest/1858/problem/B)问题建模问题分析1.分析所求2.如何快速计算每个商贩被去除后的饼干数量代码 The Walkway 问题建模
给定n个椅子其中有m个位置存在商贩在商贩处必须购买饼干吃每隔经过d个椅子需要消耗饼干在初始椅子1处也需要吃饼干现在可以去除一个商贩问去除一个商贩后所需消耗的饼干数量最小为多少以及符合要求的商贩数量。
问题分析
1.分析所求
题目需要输出一个最小的饼干数量以及对应符合要求的商贩数量。则可以考虑采用枚举计算每个商贩缺失后所需的饼干数量取数量最小的情况即可。
2.如何快速计算每个商贩被去除后的饼干数量
由于到商贩处必须买饼干也就是到商贩处计算椅子的间隔需要重新计算则只需按商贩间隔计算饼干数量即可。由于只去除一个商贩则可以预处理出所有商贩都存在的饼干数量然后计算出去除商贩所需饼干数最少的情况即可。
代码
#includebits/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 pairint, int PII;
typedef pairLL, LL PLL;
const int N 1e510, INF 0x3f3f3f3f;
int s[N];void solve() {int n,m,d;cin n m d;for(int i1;im;i) cin s[i];///计算方便计算第一个椅子和最后一个椅子到商贩的间隔s[0]1-d,s[m1]n1;int ansm;for(int i0;im;i) ans(s[i1]-s[i]-1)/d;int val0,cnt0;///计算去除商贩后减少饼干数量最多的for(int i1;im;i){int as[i]-s[i-1]-1;int bs[i1]-s[i]-1;int cs[i1]-s[i-1]-1;if(vala/db/d-c/d1) vala/db/d-c/d1,cnt1;else if(vala/db/d-c/d1) cnt;}cout ans-val cnt\n;
}int main() {int t 1;cin t;while (t--) solve();return 0;
}
