V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ttma1046
V2EX  ›  程序员

求帮忙做到题!谢谢谢谢!

  •  
  •   ttma1046 ·
    ttma1046 · 2016-02-06 13:14:12 +08:00 · 3335 次点击
    这是一个创建于 3202 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一道买车票的题

    车票有 3 种

    1 。一天的票,价格 2
    2.7 天的票,价格 7 (当天买,在当天+6 天内有效)
    3 。 30 天的票,价格 25

    写一个方法,参数是一个 int[] dates

    这个 dates 里的每一个元素是这个月几号你要坐车要买票。

    算出最便宜的买票的总价格。

    public int solution(int[] dates) {
    // 返回最便宜买票方法的总价格
    }

    假设下个月 3 月有 31 天。

    那这个 dates 最多就是 31 个元素, 0 - 30

    我 1 号, 2 号, 4 号, 5 号, 7 号, 29 号, 30 号买票
    dates[0] = 1
    dates[1] = 2
    dates[2] = 4
    dates[3] = 5
    dates[4] = 7
    dates[5] = 29
    dates[6] = 30

    那最便宜的就是买一张 7 天票,从 1 号到 7 号,加上 29 号, 30 号买两张 1 天票,一共 7+4 = 11 元

    14 条回复    2016-02-11 16:08:43 +08:00
    ttma1046
        1
    ttma1046  
    OP
       2016-02-06 13:56:55 +08:00
    求帮忙。
    pimin
        2
    pimin  
       2016-02-06 14:12:17 +08:00 via Android   ❤️ 1
    这个类似公交卡嘛
    按照你的思路来:
    1.7 天卡要达到搜 4 个元素才划算,凑> 4 的买 7 天卡;
    2.剩下元素全部买单日卡,计算总价 s1 ;
    3.s1 和月卡比价格
    yuriko
        3
    yuriko  
       2016-02-06 14:15:36 +08:00   ❤️ 1
    @ttma1046 动规吧……
    一个数组记录结算到第 i 天时的最低价格,然后第 n 天就是 m[n-7]+7 , m[n-30]+25 , m[n-1]+2,m[n-1]中间能满足当天票需求的最小值,类推完 30 天得解
    ttma1046
        4
    ttma1046  
    OP
       2016-02-06 14:22:52 +08:00
    @pimin 这是就是我写的,写得很垃圾。惨不忍睹
    ttma1046
        5
    ttma1046  
    OP
       2016-02-06 14:24:11 +08:00
    @yuriko 谢谢,能不能在详细的说点。动规我早就还给大学老师了。
    yuriko
        6
    yuriko  
       2016-02-06 14:31:21 +08:00   ❤️ 1
    @ttma1046 我还觉得说的太细了……
    m[i]表示第 i 天为止的最低支出票价
    m[0]=0 开始,目标得到 m[31]
    for i=1~31
    if (第 i 天需要票){m[i] = min(m[i-7]+7 , m[i-30]+25 , m[i-1]+2)}//注意越界取 0 即可
    else{m[i]=n[i-1]}

    基本思路就是这样不知道有没有错
    ttma1046
        7
    ttma1046  
    OP
       2016-02-06 14:47:08 +08:00
    @yuriko 你的是不是每天都要买票?题目是随机抽几天出来要去买票坐车,也能这样做吗?
    ilotuo
        8
    ilotuo  
       2016-02-06 14:55:17 +08:00
    2 楼就有答案了..
    遍历 data.length -4 次
    (data[i+3]-data[i])<7 买 7 天票
    yuriko
        9
    yuriko  
       2016-02-06 15:24:18 +08:00   ❤️ 1
    @ttma1046 你认真读一下逻辑好么,那个 if 语句你有看到么……
    3pointer
        10
    3pointer  
       2016-02-06 15:25:17 +08:00   ❤️ 1
    2 楼的意思是没错,但是这样考虑问题就复杂了。
    比如 1 , 5 , 6 , 7 , 8 , 9 肯定是不凑前四个而是后五个。
    3 楼已经给出了简单的解法,遍历一遍就行了
    ttma1046
        11
    ttma1046  
    OP
       2016-02-07 06:09:31 +08:00
    @yuriko @3pointer
    写的很垃圾,求拍砖

    public int solution(int[] selectiveDates)
    {
    int [] minCost = new int[31];

    for (int date = 0; date < 31; date++)
    {
    int oneDayAgo = 0;
    if (date - 1 > 0)
    oneDayAgo = date - 1;


    if (selectiveDates.Contains(date))
    {
    int sevenDaysAgo = 0;
    if (date - 7 > 0)
    sevenDaysAgo = date - 7;

    int thirtyDaysAgo = 0;
    if (date - 30 > 0)
    thirtyDaysAgo = date - 30;

    minCost[date] = Math.Min(minCost[sevenDaysAgo] + 7, minCost[thirtyDaysAgo] + 25);
    minCost[date] = Math.Min(minCost[date], minCost[oneDayAgo] + 2);
    }
    else
    {
    minCost[date] = minCost[oneDayAgo];
    }
    }

    return minCost[30];
    }
    ttma1046
        12
    ttma1046  
    OP
       2016-02-07 06:09:58 +08:00
    ```csharp
    public int solution(int[] selectiveDates)
    {
    int [] minCost = new int[31];

    for (int date = 0; date < 31; date++)
    {
    int oneDayAgo = 0;
    if (date - 1 > 0)
    oneDayAgo = date - 1;


    if (selectiveDates.Contains(date))
    {
    int sevenDaysAgo = 0;
    if (date - 7 > 0)
    sevenDaysAgo = date - 7;

    int thirtyDaysAgo = 0;
    if (date - 30 > 0)
    thirtyDaysAgo = date - 30;

    minCost[date] = Math.Min(minCost[sevenDaysAgo] + 7, minCost[thirtyDaysAgo] + 25);
    minCost[date] = Math.Min(minCost[date], minCost[oneDayAgo] + 2);
    }
    else
    {
    minCost[date] = minCost[oneDayAgo];
    }
    }

    return minCost[30];
    }
    ```
    sengxian
        13
    sengxian  
       2016-02-11 16:05:54 +08:00
    #include <algorithm>
    #include <iostream>
    using namespace std;

    int main() {
    bool need[31 + 1]; //需要初始化
    int dp[31 + 1];
    dp[0] = 0; //边界
    for(int i = 1; i <= 31; ++i) {
    dp[i] = dp[i - 1] + 2; //总可以买一天的票
    if(!need[i]) dp[i] = dp[i - 1];
    else dp[i] = min(dp[i], min(dp[i - 7 < 0 ? 0 : i - 7] + 7, dp[i - 30 < 0 ? 0 : i - 30] + 25));
    }
    return 0;
    }
    sengxian
        14
    sengxian  
       2016-02-11 16:08:43 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1057 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 19:38 · PVG 03:38 · LAX 11:38 · JFK 14:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.