Viết c++ giúp mình với ạ, link test mình để ở dưới ạ:
Cho dãy số nguyên a1, a2,..., an (1 < n < 100000), mỗi số không vượt quá 10000. Dãy số này được viết trên một vòng tròn. Nghĩa là, khi cắt vòng tròn tại vị trí j, ta thu được:
aj, aj+1,..., an, a1, a2,..., aj-1
Vị trí j được gọi là vị trí tốt, nếu các điều kiện sau đây được thỏa mãn:
aj > 0
aj+aj+1>0
..................
aj + aj+1 + ... + an > 0
aj + aj+1 + ... + an + a1 > 0
..........................
aj + aj+1 + ... + an + a1 + a2 + ... + aj-2>0
aj + aj+1 + ... + an + a1 + a2 + ... + aj-2 + aj-1>0
Yêu cầu: hãy đếm số vị trí tốt.
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
/* /\_/\
(= ._.)
/ >0 \>1
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a[100001], dp[100001], cnt[100002], l[100001], r[100001], kq=0;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
dp[0] = 0;
cnt[n + 1] = 0;
for (ll i = 1; i <= n; ++i)
{
cin >> a[i];
dp[i] = dp[i - 1] + a[i];
}
l[1] = a[1], r[n] = a[n];
l[0] = 0;
for (ll i = n; i >= 1; --i)
{
cnt[i] = cnt[i + 1] + a[i];
}
for (ll i = 2; i <= n; ++i)
{
l[i] = min(l[i - 1], dp[i]);
}
for (ll i = n - 1; i >= 1; --i)
{
r[i] = min(r[i + 1] + a[i], a[i]);
}
for (ll i = 1; i <= n; ++i)
{
if (r[i] > 0 and cnt[i] + l[i - 1] > 0) kq++;
}
cout << kq;
return 0;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin
317
3935
195
ê dài thế