彗星撞地球，代码爆爆爆！！！
彗星撞地球，代码爆爆爆！！！
小码匠
发布于 2022-06-16 18:15:03
发布于 2022-06-16 18:15:03
代码可运行
运行总次数：0
代码可运行
碎碎念
这是一个悲伤的故事……
当你空间爆完，时间又爆了，时间不爆了，数据类型又开错了，那么，你可能就会和我一样，自己就爆炸了，没错，就是彗星撞地球的那种爆炸……
标签
- 动态规划、二分查找
题目地址
D - Enough Array
- https://atcoder.jp/contests/abc130/tasks/abc130_d?lang=en
问题描述
一个长度为N的数列，A=a,a,…,a, 还有一个整数K, 求满足下面条件的连续子序列有多少个？
- 连续子序列的和大于等于K
但是，如果有2个子序列列都相同，但取自不同位置，也当做不同的序列计算
注意：计算出来的个数可能会超过32位整数
约束
输入
数据输入格式如下:
N K
a1 a2 ...... aN
输出
打印满足条件连续子序列个数
示例输入1
4 10
6 1 2 7
示例输出 1
2
一下的子序列满足条件，所以输出：2
- A[1..4]=a,a,a,a, with the sum of 16
- A[2..4]=a,a,a, with the sum of 10
示例输入 2
3 5
3 3 3
示例输出 2
3
注意：子序列相同，但取自不同位置，也要单独计算个数
示例输入 3
10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352
示例输出 3
36
题解
小码匠第一次提交
直接内存爆了，都是这行惹的祸，使用二维的动态大数组
通过：16 RE：13
vector<vector<int>> dp(n, vector<int>(n, 0));
ABC130-D-01
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k, temp, key;
long long ans = 0;
cin >> n >> k;
cin >> temp;
vector<vector<int>> dp(n, vector<int>(n, 0));
dp[0][0] = temp;
for(int i = 1; i < n; i++) {
cin >> temp;
for(int j = 0; j <= i; j++) {
dp[j][i] = dp[j][i - 1] + temp;
}
}
for(int i = 0; i < n; i++) {
key = lower_bound(dp[i].begin(), dp[i].end(), k) - dp[i].begin();
ans += n - key;
}
cout << ans;
}
小码匠第二次提交
- 继续优化：一维数组
- 毫不含糊，完美的超时
- 通过：16 TLE：13
ABC130-D-02
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
long long ans = 0;
long long temp;
cin >> n >> k;
vector<int>dp(n);
for(int i = 0; i < n; i++) {
cin >> dp[i];
}
for(int i = 0; i < n; i++) {
temp = 0;
for(int j = i; j < n; j++) {
temp += dp[j];
if(temp >= k) {
ans++;
}
}
}
cout << ans;
}
小码匠第三次提交
- 继续循环优化：减少循环次数
- 依然完美超时, 22：通过 7：TLE ABC130-D-03
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
long long ans = 0;
long long temp;
cin >> n >> k;
vector<int>dp(n);
for(int i = 0; i < n; i++) {
cin >> dp[i];
}
for(int i = 0; i < n; i++) {
temp = 0;
for(int j = i; j < n; j++) {
temp += dp[j];
if(temp >= k) {
ans += n - j;
break;
}
}
}
cout << ans;
}
小码匠题解：AC
- 继续优化：降时间复杂度
- 执行时间19ms以内搞定，看上面几次执行的时长，100倍的提升 ABC130-D-04
- 上次最长耗时：2105ms 本次：19ms
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long n, k;
long long ans = 0;
long long temp;
cin >> n >> k;
vector<int> a(n);
vector<long long>dp(n);
cin >> dp[0];
a[0] = dp[0];
for(int i = 1; i < n; i++) {
cin >> a[i];
dp[i] += dp[i - 1] + a[i];
}
for(int i = 0; i < n; i++) {
temp = lower_bound(dp.begin() + i, dp.end(), k) - dp.begin();
k += a[i];
if(n - temp <= 0) {
break;
} else {
ans += n - temp;
}
}
cout << ans;
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-06-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
