Trong một quán nước có M chai nước giải khát, các chai đánh số từ 1 đến M. Có N người xếp hàng chờ uống nước theo thứ tự từ 1 đến N. Lần lượt từng người, từ người số 1 đến N, mỗi người sẽ vào và uống 1 lít nước ở một trong số M chai, đương nhiên các chai uống hết sẽ không tính. Mỗi lần chỉ có 1 người vào uống. Có 2 dạng người: người hoang phí và người tiết kiệm. Người hoang phí khi vào uống sẽ chọn một trong những chai còn nhiều nước nhất để uống (mặc dù chỉ uống 1 lít). Người tiết kiệm sẽ chọn một trong những chai còn ít nước để uống. Sau khi N người uống, chủ quán thống kê lại số nước còn lại ở mỗi chai. Hãy viết hàm cài đặt bằng C++ để xác định từng người khách đã uống nước ở chai nào.
Input: Dòng 1 có 3 số nguyên N, M, K(số lít nước mỗi chai),1<=N<=100, 1<=M<=100, 1<=K<=20 . Dòng 2 có N ký tự cho biết người i là người hoang phí (W) hay tiết kiệm (E). Dòng 3 có M số cho biết số nước trong mỗi bình sau khi N người uống.
Output: Kết quả có N số, trong đó số thứ i cho biết chai nước mà người khách thứ i đã uống
Ví dụ:
Input:5 5 2 E E W W E 1 2 0 2 0Output:
3 3 5 1 5(Giải thích : khách 1 uống chai 3, khách 2 uống chai 3, khách 3 uống chai 5, khách 4 uống chai 1, khách 5 uống chai 5)
#include <iostream>
#include <vector>
using namespace std;
int findMinIndex(int a[], int n)
{
int minIndex = 0;
for (int i = 1; i < n; i++)
if (a[i] < a[minIndex])
minIndex = i;
return minIndex;
}
int findMaxIndex(int a[], int n)
{
int maxIndex = 0;
for (int i = 1; i < n; i++)
if (a[i] > a[maxIndex])
maxIndex = i;
return maxIndex;
}
// tìm vị trí của số lớn nhì, nếu tất cả các phần tử bằng nhau thì trả về 0
int findSecondMaxIndex(int a[], int n)
{
int maxIndex = findMaxIndex(a, n), secondMaxIndex;
bool check = true;
for (int i = 0; i < n; i++)
if (a[i] != a[0])
{
check = false;
break;
}
if (check)
return 0;
for (int i = 0; i < n; i++)
if (a[i] < a[maxIndex])
{
secondMaxIndex = i;
break;
}
for (int i = 0; i < n; i++)
if (a[i] > a[secondMaxIndex] && a[i] < a[maxIndex])
secondMaxIndex = i;
return secondMaxIndex;
}
void solve(int bottles[], int bottlesSize, char people[], int peopleSize, int k)
{
int minIndex, secondMaxIndex;
vector<int> res;
reverse(people, people + peopleSize);
for (int i = 0; i < peopleSize; i++)
{
if (people[i] == 'E')
{
minIndex = findMinIndex(bottles, bottlesSize);
bottles[minIndex]++;
//cout << minIndex + 1 << " " << "bottles[" << minIndex + 1 << "] = " << bottles[minIndex] << endl;
res.push_back(minIndex);
}
else
{
secondMaxIndex = findSecondMaxIndex(bottles, bottlesSize);
bottles[secondMaxIndex]++;
//cout << secondMaxIndex + 1 << " " << "bottles[" << secondMaxIndex + 1 << "] = " << bottles[secondMaxIndex] << endl;
res.push_back(secondMaxIndex);
}
}
reverse(res.begin(), res.end());
for (auto x : res)
cout << x + 1 << " ";
}
int main()
{
int n, m, k;
int bottles[100];
char people[100];
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
cin >> people[i];
for (int i = 0; i < m; i++)
cin >> bottles[i];
solve(bottles, m, people, n, k);
}
Ý tưởng: chai nước sau khi người E uống sẽ có ít nước nhất, chai nước sau khi người W uống sẽ có số nước ít hơn chai nhiều nước nhất là 1. Duyệt ngược mảng people, nếu là E thì +1 vào chai có ít nước nhất, nếu là W thì +1 vào chai có nhiều nước thứ nhì.
Code em chạy bị sai với input là 7 4 3 W E W W E W W 2 0 1 2. Mọi người xem thử ý tưởng em bị sai chỗ nào với ạ.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?