`* C++:`
`" "`
#include <iostream>
using namespace std;
int main()
{
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long n, S;
cin >> n >> S;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
int gauche = 0, droite = 0, resultat = n + 1;
long long somme = a[0];
while (1) {
if (somme < S) {
droite++;
if (droite == n)
break;
somme += a[droite];
}
else {
resultat = min(resultat, droite - gauche + 1);
somme -= a[gauche];
gauche++;
}
}
if (resultat != n + 1)
cout << resultat;
else
cout << -1;
return 0;
}
$\color{#e6ffff}{\text{___}}$ $\color{#ccffff}{\text{___}}$ $\color{#b3ffff}{\text{___}}$ $\color{#99ffff}{\text{___}}$ $\color{#80ffff}{\text{___}}$ $\color{#66ffff}{\text{___}}$ $\color{#4dffff}{\text{___}}$ $\color{#33ffff}{\text{___}}$ $\color{#1affff}{\text{___}}$ $\color{#00ffff}{\text{___}}$ $\color{#00e6e6}{\text{___}}$ $\color{#00cccc}{\text{___}}$ $\color{#00b3b3}{\text{___}}$ $\color{ #009999}{\text{___}}$ $\color{#008080}{\text{___}}$ $\color{#006666}{\text{___}}$ $\color{#004d4d}{\text{___}}$ $\color{#003333}{\text{___}}$
`" "`
• Dùng $\texttt{2}$ con trỏ gauche, droite đều có giá trị ban đầu bằng $\texttt{0}$
• $\texttt{resultat}$ có giá trị bằng $\texttt{n + 1}$, khi kết thúc chương trình nếu resultat vẫn bằng $\texttt{n + 1}$ nghĩa khi làm $\texttt{n}$ bài tập vẫn không đạt độ khó $\texttt{≥ S}$
• Nếu $\texttt{somme < S}$, nghĩa là độ khó chưa lớn hơn hoặc bằng $\texttt{S}$, tăng $\texttt{droite}$ lên $\texttt{1}$ đơn vị và cộng dồn giá trị $\texttt{a[droite]}$ vào $\texttt{somme}$
• Nếu $\texttt{somme ≥ S}$, $\texttt{resultat}$ sẽ bằng giá trị nhỏ nhất giữa $\texttt{resultat}$ và $\texttt{droite - gauche + 1}$
• Khi $\texttt{somme ≥ S}$, giảm $\texttt{a[gauche]}$ từ $\texttt{somme}$ và tăng $\texttt{gauche}$ lên $\texttt{1}$, nghĩa khi độ khó đã lớn hơn hoặc bằng $\texttt{S}$, thử trừ đi độ khó $\texttt{a[gauche]}$ để xem với số lượng bài tập ít hơn thì độ khó có còn đạt yêu cầu hay không
• Vòng lặp dừng khi giá trị con trỏ $\texttt{droite}$ bằng $\texttt{n}$
#include <bits/stdc++.h>
using namespace std;
long long a[10000005], t[10000005], n, ans, s;
int main() {
cin >> n >> s;
for (long long i = 1; i <= n; ++i) cin >> a[i];
for (long long i = 1; i <= n; ++i)
{
t[i] = t[i - 1] + a[i];
}
ans = n;
for (long long i = 1; i <= n; ++i)
{
if (s <= t[i])
{
long long j = upper_bound(t, t + i, t[i] - s) - t - 1;
ans = min(ans , i - j);
}
}
if (ans == n) cout << "-1";
else cout << ans;
return 0;
}
Tin học là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng. Tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin. Hãy tận dụng sức mạnh của tin học để giải quyết các vấn đề và sáng tạo ra những giải pháp mới!
Lớp 9 - Là năm cuối ở cấp trung học cơ sở, chúng ta sắp phải bước vào một kỳ thi căng thẳng và sắp chia tay bạn bè, thầy cô. Áp lực từ kỳ vọng của phụ huynh và tương lai lên cấp 3 thật là lớn, nhưng hãy tin vào bản thân và giữ vững sự tự tin!
Copyright © 2024 Giai BT SGK