算法
(暴力枚举) $O(n)$
我们可以用last记录从开始到现在还剩有多少草,这样每次比较枚举的i和i+1的天数之差和last的最小值,答案加上这个值,不要忘了last每次要减去i到i+1要经历的天数。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
LL n, m, t;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>t;
vector<PLL> w(n + 2, {0, 0});
rep(i, 1, n) cin>>w[i].fi>>w[i].se;
w[n + 1].fi = t + 1, w[0].fi = 1;
LL res = 0, last = 0;
rep(i, 0, n)
{
last += w[i].se;
res += min(last, w[i + 1].fi - w[i].fi);
last = max(0ll, last - (w[i + 1].fi - w[i].fi));
// cout<<res<<" "<<last<<endl;
}
cout<<res<<endl;
return 0;
}
Java 代码
import java.util.*;
public class Main{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long k = sc.nextLong();
long[] d = new long[n + 10];
long[] t = new long[n + 10];
for(int i=1;i<=n;i++) {d[i] = sc.nextLong();t[i] = sc.nextLong();}
d[0] = 1;d[n + 1] = k + 1;
long res = 0, last = 0;
for(int i=0;i<=n;i++)
{
last += t[i];
res += Math.min(last, d[i+1] - d[i]);
last = Math.max(0, last - (d[i+1] - d[i]));
}
System.out.println(res);
}
}
Python 代码
n, k = map(int, input().split())
d, t = [0] * (n + 2), [0] * (n + 2)
for i in range(1, n + 1): d[i], t[i] = map(int, input().split())
res, last = 0, 0
d[0], d[n + 1] = 1, k + 1
for i in range(n + 1):
last += t[i]
res += min(last, d[i + 1] - d[i])
last = max(0, last - (d[i + 1] - d[i]))
print(res)