---
tags: LQDOJ
title: CaiWinDao và 3 em gái
author: Editorial-Slayers Team
license: Public domain
---

<style>
.markdown-body { max-width: 2048px; }
</style>

$\Huge \text{🌱 CaiWinDao và 3 em gái}$

-----

###### 🔗 Link: [[CaiWinDao và 3 em gái](https://lqdoj.edu.vn/problem/sisters)]
###### 📌 Tags: Greedy
###### 👤 Writter: @thanhchauns2
###### 👥 Contributor:
###### 📋 Content:

[TOC]

-----
## Hướng dẫn
Gọi tổng số kẹo là $X$, số dư của phép chia $\frac{X}{3}$ is $Y$, bài toán có thể được chia thành một vài trường hợp:
Case 1: Nếu ($Y = 0$), lấy toàn bộ số kẹo.
Case 2: Nếu ($Y = 1$):
- Loại bỏ một túi với số lượng kẹo chia $3$ dư $1$, hoặc
- Loại bỏ hai túi với số lượng kẹo chia $3$ dư $2$.
Case 3: Nếu ($Y = 2$):
- Loại bỏ một túi với số lượng kẹo chia $3$ dư $2$, hoặc
- Loại bỏ hai túi với số lượng kẹo chia $3$ dư $1$.
Tất nhiên chúng ta cần check tính khả thi của các trường hợp, hoặc đáp án sẽ bị sai.

-----
### Code

> **Time:** $O(nlogn)$
> **Space:** $O(n)$
> **Algo:** sorting
> [color=lightgreen]

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;
signed main()
{
    int a;
    cin >> a;
    long long ans = 0;
    vector<long long> C[3];
    for (int i = 0; i < a; i++)
    {
        long long x;
        cin >> x;
        ans += x;
        C[x % 3].push_back(x);
    }
    for (int i = 0; i < 3; i++) sort(C[i].begin(), C[i].end());
    if (ans % 3 == 0)
    {
        cout << ans / 3 << endl;
        return 0;
    }
    if (ans % 3 == 1)
    {
        long long k = 1e17, q = 1e17;
        if (!C[1].empty()) k = C[1][0];
        if (C[2].size() > 1) q = C[2][0] + C[2][1];
        cout << (ans - min(k, q)) / 3 << endl;
        return 0;
    }
    if (ans % 3 == 2)
    {
        long long k = 1e17, q = 1e17;
        if (!C[2].empty()) k = C[2][0];
        if (C[1].size() > 1) q = C[1][0] + C[1][1];
        cout << (ans - min(k, q)) / 3 << endl;
        return 0;
    }
}

:::

-----
## Bonus

Bạn có thể giải với trường hợp mỗi gói kẹo chỉ chia cho 1 người không?