『ACM C++』HDU杭電OJ | 1415 - Jugs （灌水定理引申）

来源:https://www.cnblogs.com/winniy/archive/2019/02/24/10428708.html
-Advertisement-
Play Games

今天總算開學了，當了班長就是麻煩，明明自己沒買書卻要帶著一波人去領書，那能怎麼辦呢，只能說我善人心腸哈哈哈，不過我腦子裡突然浮起一個念頭，大二還要不要繼續當這個班委呢，既然已經體驗過就可以適當放下了吧，用心在自己的研究上。晚上級會開完也就八點多了，開始打打題，今天在HDU杭電的ACM集訓題看到一個奇 ...


　　今天總算開學了，當了班長就是麻煩，明明自己沒買書卻要帶著一波人去領書，那能怎麼辦呢，只能說我善人心腸哈哈哈，不過我腦子裡突然浮起一個念頭，大二還要不要繼續當這個班委呢，既然已經體驗過就可以適當放下了吧，用心在自己的研究上。晚上級會開完也就八點多了，開始打打題，今天在HDU杭電的ACM集訓題看到一個奇葩的題，前來獻上。

 

 

今日推薦：

《全球風暴》 一部宇宙航空和地球氣候片的良心佳作，後期特效建模都是特別杠杠的大片，不會讓你失望的喲，我已經三刷了哈哈哈。這部片在愛奇藝有上線，有興趣的朋友可以看看鴨。

愛奇藝鏈接：https://www.iqiyi.com/v_19rr7pl8vg.html

 

 

------------------------------------------------題目----------------------------------------------------------

Jugs

Problem Description

　　In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes that puzzle.
You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use: (1) you can fill a jug, (2) you can empty a jug, and (3) you can pour from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.
A problem is given by a triple (Ca,Cb,N), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. A solution is a sequence of steps that leaves exactly N gallons in jug B. The possible steps are
fill A
fill B
empty A
empty B
pour A B
pour B A
success
where "pour A B" means "pour the contents of jug A into jug B", and "success" means that the goal has been accomplished.
You may assume that the input you are given does have a solution.

Input

　　Input to your program consists of a series of input lines each defining one puzzle. Input for each puzzle is a single line of three positive integers: Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the goal. You can assume 0 < Ca <= Cb and N <= Cb <=1000 and that A and B are relatively prime to one another.

Output

　　Output from your program will consist of a series of instructions from the list of the potential output lines which will result in either of the jugs containing exactly N gallons of water. The last line of output for each puzzle should be the line "success". Output lines start in column 1 and there should be no empty lines nor any trailing spaces.

Sample Input

3 5 4 5 7 3

Sample Output

fill B
pour B A
empty A
pour B A
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
empty B
pour A B
success

------------------------------------------------題目----------------------------------------------------------

 

（一） 原題大意：

　　　　你有兩個杯子，A、B；你只有三種操作，（1）清空任何一個杯子 （2）當被子是空的時候可以填滿任何一個杯子  （3）將某一杯的水倒到另一杯中（不會溢出計算）直到B杯達到目標數Aim C。

　　　　輸入的A、B升數有要求，一定需要相鄰互質。並且A小於B，且目標數Aim C要小於B即可。

　　　　題目好像想象挺容易，手寫也好像能解出來，但就是電腦老是犯傻逼。扔HDU的OJ上老是顯示超時，我看了一下時間限制也很足夠啊：

　　　　Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

　　　　後來我發現坑在哪裡了。

　　　　這道題我居然在一個小學課本的趣味題發現的，真的是，現在的小學益智題怕是很多都能改成編程題了，而且改了編程題之後你還不一定解的出來哈哈哈。

 

（二） 題目分析：

　　　　其實方法很簡單，你們可以試一下下麵這個步驟，是一定能得到結果的：

　　　　（1）裝滿A

　　　　（2）從A倒B

　　　　（3）如果B滿了清空

　　　　基本以上三個步驟都能找打準確的結果。

　　　　這就是經典的“灌水定理”，這裡提一下，在下麵我會引出這個定理，理論上倒水的步驟是不唯一的，所以我就太在意樣例。

　　　　然而在無數次交OJ的時候瘋狂的WA超時，我終於從樣例發現了不對勁。在其他OJ上是可以過的，但在HDU OJ好像並沒有被智能處理化：

　　　　如果目標數C小於A，必須從A開始倒滿。如果目標數C大於A，則必須從B開始倒滿。原因是為了尋求最短步驟操作，拿樣例來說，3 5 4，如果先倒A，那麼你需要八步，而如果先到B，那麼你需要六步，所以這道題杭電OJ是預設要求最短步驟了，題目並沒有說，所以害我 一股腦熱直接從A迴圈交，就錯了。

 

（三） 代碼分塊：

　　　　首先：我先構造三個步驟出來：Fill、Pour、Empty

void pour(bool x)
{
    if(x)
    {
        if(cap_b + cap_a <= temp_b)
        {
            cap_b = cap_b + cap_a;
            cap_a = 0;
        }
        else
        {
            cap_a  = cap_a - (temp_b - cap_b);
            cap_b = temp_b;
        }
        printf("pour A B\n");
    }
    
    else
    {
        if(cap_b + cap_a <= temp_a)
        {
            cap_a = cap_b + cap_a;
            cap_b = 0;
        }
        else
        {
            cap_b  = cap_b - (temp_a - cap_a);
            cap_a = temp_a;
        }
        printf("pour B A\n");
    }
}
void fill(bool x)
{
    if(x)
    {
        cap_a = temp_a;
        printf("fill A\n");
    }
    else
    {
        cap_b = temp_b;
        printf("fill B\n");
    }
 }
 void empty(bool x)
{
    if(x)
    {
    cap_b = 0;
    printf("empty B\n");
    }
    else
    {    
    cap_a = 0;
    printf("empty A\n");
    }
 }

　　其中x為真是以A為主，為假時是B為主操作。難點應該在於Pour傾倒函數的書寫，你需要區分從A倒到B時，是否B滿了，如果滿了就不能倒，A要留剩下，如果沒滿，就相當於把A清空了。這是要註意的地方。

　　第二步：特殊處理

        if(aim == 0)
        {
            printf("success\n");
            continue;
        }
        if(temp_b == aim)
        {
            printf("fill B\n");
            printf("success\n");
            continue;
        }
        if(temp_a == aim)
        {
            printf("fill A\n");
            printf("pour A B\n");
            printf("success\n");
            continue;
        }

　　這個就是我超時的原因之一了，因為我沒有考慮到 3 5 3 或者是 3 5 5這種情況，當目標數直接等於其中一個杯子量時的操作，就會讓程式一直迴圈操作得不到結果超時了。各位要註意。

　　第三步：進行迴圈了

            if(temp_a >= aim)
            {
                if(cap_a == 0) fill(true);
                pour(true);
                if(cap_b == temp_b) empty(true);
            }
            else
            {
                if(cap_b == 0) fill(false);
                pour(false);
                if(cap_a == temp_a && cap_b != aim) empty(false);
            }

　　這裡就要提到我剛剛分析的時候說的最短步驟問題了，如果目標數C小於A，必須從A開始倒滿。如果目標數C大於A，則必須從B開始倒滿。就在這裡體現，核心步驟其實很簡單，就是剛剛的三步，填滿、移動、清空已滿。

　　第四步：得到結果退出永真迴圈

            if(cap_a == aim)
            {
                if(cap_b != 0) printf("empty B\n");
                printf("pour A B\n");
                printf("success\n");
                break;
            }
            if(cap_b == aim)
            {
                printf("success\n");
                break;
            }

 

（四） AC代碼：

#include<bits/stdc++.h>
using namespace std;
int temp_a,temp_b,aim;
int cap_a,cap_b;
void pour(bool x)
{
    if(x)
    {
        if(cap_b + cap_a <= temp_b)
        {
            cap_b = cap_b + cap_a;
            cap_a = 0;
        }
        else
        {
            cap_a  = cap_a - (temp_b - cap_b);
            cap_b = temp_b;
        }
        printf("pour A B\n");
    }
    
    else
    {
        if(cap_b + cap_a <= temp_a)
        {
            cap_a = cap_b + cap_a;
            cap_b = 0;
        }
        else
        {
            cap_b  = cap_b - (temp_a - cap_a);
            cap_a = temp_a;
        }
        printf("pour B A\n");
    }
}
void fill(bool x)
{
    if(x)
    {
        cap_a = temp_a;
        printf("fill A\n");
    }
    else
    {
        cap_b = temp_b;
        printf("fill B\n");
    }
 }
 void empty(bool x)
{
    if(x)
    {
    cap_b = 0;
    printf("empty B\n");
    }
    else
    {    
    cap_a = 0;
    printf("empty A\n");
    }
 }
int main()
{
    while(~scanf("%d %d %d",&temp_a,&temp_b,&aim))
    {
        if(aim == 0)
        {
            printf("success\n");
            continue;
        }
        if(temp_b == aim)
        {
            printf("fill B\n");
            printf("success\n");
            continue;
        }
        if(temp_a == aim)
        {
            printf("fill A\n");
            printf("pour A B\n");
            printf("success\n");
            continue;
        }
        
        cap_a = cap_b = 0;//記得每個樣例要清空杯子 
        for(;;)
        {
            if(temp_a >= aim)
            {
                if(cap_a == 0) fill(true);
                pour(true);
                if(cap_b == temp_b) empty(true);
            }
            else
            {
                if(cap_b == 0) fill(false);
                pour(false);
                if(cap_a == temp_a && cap_b != aim) empty(false);
            }
            if(cap_a == aim)
            {
                if(cap_b != 0) printf("empty B\n");
                printf("pour A B\n");
                printf("success\n");
                break;
            }
            if(cap_b == aim)
            {
                printf("success\n");
                break;
            }
         } 
    }
    return 0;
}

 

（五）AC截圖：

 

（六） 解後分析：

　　　　這道題如果不要求最短路徑的話，其實就是非常簡單的題目了，只要迴圈那三個步驟肯定能出結果，而且代碼量直接大大減少。不過這道題解法我是比較直接的一種解法，在解後去網上找找別的解法，那就是還有一種就是用BFS（寬度優先搜索）

　　　　代碼貼上：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int MAXN=1050;
struct node{
    int a,b;
    node(int _a,int _b):a(_a),b(_b){}
};
int A,B,N;
int vis[MAXN][MAXN];
vector<int> path[MAXN][MAXN];
void op(int &a,int &b,int i){
    switch(i){
        case 1:{
            a=A;
            break;
        }
        case 2:{
            b=B;
            break;
        }
        case 3:{
            a=0;
            break;
        }
        case 4:{
            b=0;
            break;
        }
        case 5:{
            if(a+b>B){
                a=(a+b)-B;
                b=B;
            }
            else{
                b+=a;
                a=0;
            }
            break;
        }
        case 6:{
            if(b+a>A){
                b=(b+a)-A;
                a=A;
            }
            else{
                a+=b;
                b=0;
            }
            break;
        }
    }
}
void op_print(int i){
    switch(i){
        case 1:{
            printf("fill A\n");
            break;
        }
        case 2:{
            printf("fill B\n");
            break;
        }
        case 3:{
            printf("empty A\n");
            break;
        }
        case 4:{
            printf("empty B\n");
            break;
        }
        case 5:{
            printf("pour A B\n");
            break;
        }
        case 6:{
            printf("pour B A\n");
            break;
        }
    }
}
void bfs(){
    memset(vis,-1,sizeof(vis));
    for(int i=0;i<A;i++){
        for(int j=0;j<B;j++){
            path[i][j].clear();
        }
    }
    queue<node> que;
    que.push(node(0,0));
    vis[0][0]=0;
    while(!que.empty()){
        node tmp=que.front();
        que.pop();
        int ta=tmp.a;
        int tb=tmp.b;
        if(tb==N){
            for(int i=0;i<path[ta][tb].size();i++){
                op_print(path[ta][tb][i]);
            }
            printf("success\n");
            return;
        }
        for(int i=1;i<=6;i++){
            int ta=tmp.a;
            int tb=tmp.b;
            op(ta,tb,i);
            if(vis[ta][tb]==-1){
                vis[ta][tb]=vis[tmp.a][tmp.b]+1;
                for(int j=0;j<vis[tmp.a][tmp.b];j++){
                    path[ta][tb].push_back(path[tmp.a][tmp.b][j]);
                }
                path[ta][tb].push_back(i);
                que.push(node(ta,tb));
            }
        }
    }
}
int main(void){
    while(~scanf("%d%d%d",&A,&B,&N)){
        bfs();
    }
    return 0;
}

參考：https://blog.csdn.net/westbrook1998/article/details/80937164

　　好了由於時間關係，先寫在這，因為要睡覺了hhhh，明天滿課，從早八點到晚九點半，要死，所以還是先早睡啦~

　　（1）大數計算：加減乘除乘方開根問題

　　（2）BFS搜索演算法瞭解

　　（3）灌水定理研究

　　這是這周的任務了吧，這周解決這三個點！！~~

 

註：如果有更好的解法，真心希望您能夠評論留言貼上您的代碼呢~互相幫助互相鼓勵才能成長鴨~~


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 服務註冊中心之ZooKeeper系列(一)
    一、服務註冊中心介紹 分散式服務框架部署在多台不同的機器上。例如服務A是訂單相關的處理服務，服務B是訂單的客戶的相關信息服務。此時有個需求需要在服務A中獲取訂單客戶的信息。如下圖： 此時就面臨以下幾個問題： 1、集群A中的服務調用者如何發現集群B中的服務提供者。 2、集群A中的服務調用者如何選擇集群 ...
  • 分散式系統進化歷史
    一個成熟的大型分散式系統，並不是在其開始時，就設計為這樣，而是在之後的不斷優化，迭代而不斷的進化成熟的。 在一個系統剛開始運行時，可能用戶數，業務處理等都還比較簡單，因此由一臺伺服器就能支撐起其正常的業務處理。其系統架構模型可能如下所示： 1，單應用架構 其應用服務和資料庫服務，都部署在同一臺伺服器 ...
  • 關於微服務架構的個人理解（一）
    前言：這段時間項目組正在加班加點的進行基於現有單體應用的微服務架構改造。微服務是一種架構概念，這個概念是2012年出現的，作為加快Web和移動應用程式開發進程的一種方法，2014年開始受到各方的關註，而2015年，可以說是微服務的元年；越來越多的論壇、社區、blog以及互聯網行業巨頭開始對微服務進行 ...
  • fio是如何運行的？
    本文主要介紹fio是如何運行的，並且以單線程、單job為例 fio的入口在fio.c中的main函數,下麵列出了main函數，此處只出示了一些調用的關鍵函數 在main函數中主要調用了兩個關鍵函數，parse_options，顧名思義，就是分析options，也就是fio的參數，而fio_backe ...
  • 我爬了《流浪地球》十萬個短評得出以下結論
    前言 最近大家討論最多的就是《流浪地球》了，偶爾刷逼乎，狗血的事情也是層出不窮，各種撕逼大戰，有興趣的小伙伴可以自行搜索。 截止目前，《流浪地球》已上映20天，累計票房43.94億，豆瓣評分7.9分。博主是正月初七看的，票價有點小貴，整體效果還算可以，雖然劇情有點尷尬，各種鏡頭切換有時候看的稀里糊塗 ...
  • Pandas 基礎(9) - 組合方法 merge
    首先, 還是以天氣為例, 準備如下數據: 輸出: 上面的例子就是以 'city' 為基準對兩個 dataframe 進行合併, 但是兩組數據都是高度一致, 下麵調整一下: 輸出:從輸出我們看出, 通過 merge 合併, 會取兩個數據的交集. 那麼, 我們應該可以設想到, 可以通過調整參數, 來達到 ...
  • django中url路由配置及渲染方式
    今天我們學習如何配置url、如何傳參、如何命名、以及渲染的方式，內容大致有以下幾個方面。 創建視圖函數並訪問 創建app django中url規則 捕獲參數 路徑轉換器 正則表達式 額外參數 渲染方式 創建視圖並訪問 項目中自帶的Python文件中，並沒有帶有視圖，因此我們自己創建一個，通常，我們把 ...
  • python學習筆記（0）英語單詞積累
    interpreter 解釋器 authentication 認證 Location 定位 invalid 無效的 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類