# **Tham Lam**
**Bài 3: Bus**
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,t,k,A[100005],B[100005],d = 0,sum = 0,maxx = INT_MIN;
int main() {
cin >> n >> m;
for (int i = 1; i<= n; ++i) {
cin >> t;
cin >> k;
for (int j = 1; j <= k ; ++j) {
cin >> A[j];
d++;
if (A[j] - sum >= 0) B[d] = A[j] - sum;
else B[d] = 0;
}
sum += t;
}
sort(B+1,B+d+1);
cout << sum+B[m];
// Thằng đầu tiên tốn B[1] thời gian, thằng thứ m tốn B[m] thời gian vì đã sắp xếp
// tăng dần nên thời gian ngắn nhất để xếp m thằng vào là B[m]
return 0;
}
```
# **Tìm Kiếm Nhị Phân**
**Bài 1: Hàng cây – Cưa máy**
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[1000001],m,l,r,res=0;
long long sum(int h)
{
long long res=0;
for (int i=1;i<=n;i++)
{
if (a[i]<=h) return res;
else res+=(a[i]-h);
}
return res;
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1,greater<int>());
l=a[n];r=a[1];
while (l<=r)
{
int mid=(l+r)/2;
if (sum(mid)<m) r=mid-1;
else
{
res=mid;
l=mid+1;
}
}
cout<<res;
}
```
# **Quy Hoạch Động**
* **Knapsack**
**Bài 3: Chia Kẹo**
- Chưa Truy Vết
```cpp
#include <bits/stdc++.h>
using namespace std;
bool F[100005];
int n,s = 0,A[105];
int main() {
memset(F,false,sizeof(F));
F[0] = true;
cin >> n;
for (int i = 1; i <= n; ++i ) {
cin >> A[i];
s += A[i];
}
for (int i = 1; i <= n; ++i)
for (int j = s; j >= A[i]; --j)
if (F[j - A[i]])
F[j] = true;
for (int i = s/2; i >= 1; i--) if (F[i]) {
cout << s - (i*2);
exit(0);
}
return 0;
}
```
* **Không Phải Knapsack**
**Bài 3: Bitcoin**
```cpp
#include <bits/stdc++.h>
using namespace std;
double F[105],A[105],x;
int n,t;
bool Fr[105];
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
for (int i = 1; i <= t; ++i) {
cin >> n >> x;
for (int j = 1; j <= n; ++j) cin >> A[j];
F[0] = x;
for (int j = 1; j <= n; ++j) {
F[j] = F[j-1];
for (int k = j-1; k >= 1; --k)
F[j] = max(F[j],F[k]/A[k]*A[j]-F[k]/50);
}
cout << setprecision(5) << fixed << F[n] << "\n";
}
return 0;
}
```
# **Đồ Thị**
**Bài 5: Ông Bà Già Ngâu**
* Cách 1: Dùng danh sách kề
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,d1[1005],d2[1005],minn = INT_MAX,kq,u,v,w;
vector<pair<int,int>> ke[1005];
bool Fr[1005];
void djs(int s, int d[]) {
for (int i = 1; i <= n; ++i) {
d[i] = INT_MAX;
Fr[i] = true;
}
d[s] = 0;
while (true) {
int u = 0, minn = INT_MAX;
for (int i = 1; i <= n; ++i)
if (Fr[i] && minn > d[i]) {
u = i;
minn = d[i];
}
Fr[u] = false;
if (u == 0) break;
for (pair<int,int> v : ke[u])
if (Fr[v.second] && v.first + d[u] < d[v.second]) {
d[v.second] = d[u] + v.first;
}
}
}
int main() {
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; ++i) {
cin >> u >> v >> w;
ke[u].push_back({w,v});
ke[v].push_back({w,u});
}
djs(s,d1);
djs(t,d2);
for (int i = 1; i <= n; ++i)
if (d1[i] == d2[i] && d1[i] < minn) {
minn = d1[i];
kq = i;
}
if (kq != 0) cout << kq;
else cout << "CRY";
return 0;
}
```
* Cách 2: Dùng mảng lưu trọng số
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,d1[10005],d2[10005],minn = INT_MAX,kq,u,v,w,A[1005][1005];
bool Fr[10005];
void djs(int s, int d[]) {
for (int i = 1; i <= n; ++i) {
d[i] = INT_MAX;
Fr[i] = true;
}
d[s] = 0;
while (true) {
int u = 0, minn = INT_MAX;
for (int i = 1; i <= n; ++i)
if (Fr[i] && minn > d[i]) {
u = i;
minn = d[i];
}
Fr[u] = false;
if (u == 0) break;
for (int v = 1; v <= n; ++v)
if (Fr[v] && u != v && A[u][v] != INT_MAX && A[u][v] + d[u] < d[v])
d[v] = A[u][v] + d[u];
}
}
int main() {
cin >> n >> m >> s >> t;
memset(A,INT_MAX,sizeof(A));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) if (i == j) A[i][j] = 0;
else A[i][j] = INT_MAX;
for (int i = 1; i <= m; ++i) {
cin >> u >> v >> w;
A[u][v] = A[v][u] = w;
}
djs(s,d1);
djs(t,d2);
for (int i = 1; i <= n; ++i)
if (d1[i] == d2[i] && d1[i] < minn) {
minn = d1[i];
kq = i;
}
if (kq != 0) cout << kq;
else cout << "CRY";
return 0;
}
```
**Bài 7: Hệ thống đảo cung cấp xăng**
```cpp
#include <bits/stdc++.h>
using namespace std;
int f,l,n,m,x,y,Q[100000],trace[10000],temp,temp2,d = 1,cnt = 0,A[10000],B[10000],C[10000];
vector<int> ke[10000];
bool visit[10000] = {false};
void truyvet(int v) {
temp2 = trace[v];
while (trace[temp2] != -1) {
cnt ++;
C[cnt] = temp2;
//cout << temp2 << endl;
temp2 = trace[temp2];
}
cout << cnt << "\n";
for (int i = cnt; i>=1; i--) cout << C[i] << " " ;
}
void bfs(int s) {
f = l = 1;
Q[l] = s;
trace[s] = -1;
visit[s] = true;
while (f <= l) {
temp = Q[f];
f++;
for (int v : ke[temp]) if (! visit[v]) {
visit[v] = true;
trace[v] = temp;
l++;
Q[l] = v;
if (v == y ) {
truyvet(v);
exit(0);
}
}
}
}
int power(int a) {
return a*a;
}
int main() {
cin >> n >> m >> x >> y;
for (int i = 1; i <= n; ++i) cin >> A[i] >> B[i];
for (int i = 1; i<= n-1; ++i)
for (int j = i +1; j<= n; ++j)
if ((power(A[j]-A[i]) + power(B[j]-B[i])) < power(m)){
ke[i].push_back(j);
ke[j].push_back(i);
}
bfs(x);
cout << "-1";
return 0;
}
```
Sign in with Wallet
Connect another wallet