签到题,但是出现了一些问题,测试用例2一直没搞出来
思路很容易想到,汽车油量必须保证能够通过任意相邻的两个加油站,也就是数组里的a[i]-a[i-1]的距离,特殊的,第一次需要将a[0]=0这样进行初始化,其他的使数组从1开始赋值,对应从第一个加油站开始。
特殊的,需要对最后一个加油站后面知道x终点之间的距离进行特判,因为是往返两程之和,所以需要*2
用vector存进去然后从大到小排序 最大值即为最小容量
// Problem: A. Line Trip // Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2) // URL: https://codeforces.com/contest/1901/problem/0 // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<iostream> #include<algorithm> #include<cmath> #include<vector> #include<map> #include<queue> #include<deque> #include<stack> #include<set> #include<utility> #include<iomanip> #include<string> #define int long long #define endl '\n' using namespace std; const int N=100010; const int N1=55; //cout << fixed << setprecision(2) << 3.1415 << endl; //cin.tie(nullptr)->s ync_with_stdio(0); bool cmp(int x,int y){ return x>y; } void solve(){ int n,x; vector<int> b; int a[N1]; cin>>n>>x; a[0]=0; for(int i=1;i<=n;i++) { cin>>a[i]; b.push_back(a[i]-a[i-1]); } b.push_back((x-a[n])*2); sort(b.begin(),b.end(),cmp); cout<<b.front()<<endl; } signed main(){ int _=1; cin>>_; while(_--) solve(); return 0; }
B题本来想的很简单,只需要有零的时候加一,然后找到最大值加上最大值-1那么多就是结果
但是感觉太天真了,吕文钦的思路是分组,以0为每组之间的间隔,这样每组需要移动的次数就是每组最大值-1,再加上0的个数即可,但他测试样例2没过
蒋涛的代码:
后面再补,先交一下省的又没了
- Educational Codeforces Round Rated 158educational codeforces round rated educational codeforces round 158 round codeforces rated based educational codeforces round 151 construction educational codeforces round rated 158 div for cf-educational educational codeforces round educational codeforces round 147 educational codeforces contest round educational codeforces monsters round