当前位置: 代码迷 >> 综合 >> CodeForces 66E Petya and Post (线性DP+数学思维)
  详细解决方案

CodeForces 66E Petya and Post (线性DP+数学思维)

热度:19   发布时间:2023-11-15 13:30:27.0

题目链接:http://codeforces.com/problemset/problem/66/E

#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))#define pii pair<ll,ll>
#define mk(x,y) make_pair(x,y)const int  maxn =1e5+5;
const int mod=1e9+7;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}/*
题目大意:经典加油问题,
每个站可以加ai油,一段路可以消耗bi油,最后是一个环路,
问从哪些站点出发可以走完一整个环。这道题可以自己手动模拟下,
模拟大概两三次就周到规律了,
假设现在是顺时针绕环,
那么dp[i]=dp[i+1]+a[i]-b[i],
为什么会有这个关系呢?
可以借助函数图像来思考,
少了出发点的话函数图像整体
上移一段,我们这样维护最小值即可
用dp[i]表示从i点出发回到i点的油量的最小值。
这样思路就清晰了,逆时针也是一样的。时间复杂度:O(n).*/int a[maxn],b[maxn],n;
int dp[maxn],vis[maxn];
vector<int> ans;int main()
{scanf("%d",&n);rep(i,1,n+1) scanf("%d",&a[i]);rep(i,1,n+1) scanf("%d",&b[i]);int minv=0,tmp=0;mst(vis,0);rep(i,1,n+1){tmp+=a[i]-b[i];minv=min(minv,tmp);}dp[1]=dp[n+1]=minv;for(int i=n;i>=1;i--){dp[i]=dp[i+1]+a[i]-b[i];if(dp[i]>=0) vis[i]=1;}minv=0,tmp=0,b[0]=b[n];mst(dp,0);for(int i=n;i>=1;i--){tmp+=a[i]-b[i-1];minv=min(minv,tmp);}dp[n]=dp[0]=minv;rep(i,1,n+1){dp[i]=dp[i-1]+a[i]-b[i-1];if(dp[i]>=0) vis[i]=1;}rep(i,1,n+1) if(vis[i]) ans.push_back(i);printf("%d\n",ans.size());rep(i,0,ans.size()) printf("%d ",ans[i]);return 0;
}

 

  相关解决方案