<span>codeforces730D Running Over The Bridges（模拟）</span>
题意：
给你n段连续的路，每条路有长度和最长通过时间，你正常速度为0.5，吃药速度为1，药效持续时间为r
问你走完这段路需要吃多少药，无解输出-1，吃药的数量不大于1e5则输出每个吃药的时间
思路：
模拟一遍过程，必须吃的时候吃就好了，不知道为什么过的人好少。。
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <unordered_map> #include <string> #include <time.h> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define pii pair<int,int> #define mkp make_pair #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=2e5+10; int n,cnt,l[N],t[N]; LL r,sum,ans[N]; bool solve() { for(int i=1;i<=n;i++) if(l[i]>t[i]) return 0; LL re=0,now=0; for(int i=1; i<=n; i++) { if(re>=l[i]){re-=l[i];now+=l[i];continue;} l[i]-=re;t[i]-=re;now+=re;re=0; if(l[i]*2<=t[i]){now+=l[i]*2;continue;} int x=2*l[i]-t[i]; now+=t[i]-x; sum+=x/r; if(x%r) sum++; while(cnt<100000) { ans[++cnt]=now; if(x>=r){now+=r;x-=r;if(!x)break;} else break; } x%=r;now+=x; if(x) re=r-x; } return 1; } int main() { scanf("%d%lld",&n,&r); rep(i,1,n) scanf("%d",&l[i]); rep(i,1,n) scanf("%d",&t[i]); if(!solve()) printf("-1\n"); else { printf("%lld\n",sum); if(sum<=100000) for(int i=1; i<=cnt; i++) printf("%lld ",ans[i]); } return 0; }
查看9道真题和解析
