首页 > ACM题库 > HDU-杭电 > HDU 4011-Working in Beijing-贪心-[解题报告]HOJ
2015
04-15

HDU 4011-Working in Beijing-贪心-[解题报告]HOJ

Working in Beijing

问题描述 :

Mr. M is an undergraduate student of FDU. He finds an intern position in Beijing, so that he cannot attend all the college activities. But in some conditions, he must come back to Shanghai on certain date. We can assume the important activities that Mr. M must attend are occupy a whole day. Mr. M must take flight to Shanghai before that day and leave after that day. On the other hand, Mr. M is absent in Beijing and he will lose his salary for his absent.
Sometimes the cost of flight is much higher than the loss of salary, so to save the cost on the travel, Mr. M can stay in Shanghai to wait for another important date before he back to Beijing.
Now, Mr. M knows all of the important date in the next year. Help him schedule his travel to optimize the cost.

输入:

The input contains several test cases. The first line of single integer indicates the number of test cases.
  For each test case, the first line contains three integers: n, a and b, denoting the number of important events, the cost of a single flight from Beijing to Shanghai or Shanghai to Beijing and the salary for a single day stay in Beijing. (1 <= n <= 100000, 1 <= a <= 1000000000, 1 <= b <=100)
  Next line contains n integers ti, denoting the time of the important events. You can assume the ti are in increasing order and they are different from each other. (0 <= ti <= 10000000)

输出:

The input contains several test cases. The first line of single integer indicates the number of test cases.
  For each test case, the first line contains three integers: n, a and b, denoting the number of important events, the cost of a single flight from Beijing to Shanghai or Shanghai to Beijing and the salary for a single day stay in Beijing. (1 <= n <= 100000, 1 <= a <= 1000000000, 1 <= b <=100)
  Next line contains n integers ti, denoting the time of the important events. You can assume the ti are in increasing order and they are different from each other. (0 <= ti <= 10000000)

样例输入:

2
1 10 10
5
5 10 2
5 10 15 65 70

样例输出:

Case #1: 30
Case #2: 74


点击打开链接hdu4011

水贪心:

注意I64d!

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#define PI acos(-1.0)
#define eps 1e-8
#define LL long long
#define moo 1000000007
#define INF -999999999
using namespace std;
#define maxn 101000
int main()
{
    int t;
    cin>>t;
    int n,b;
    long long sum,ans,a;
    int s[maxn];
    int Case=1;
    while(t--)
    {
        scanf("%d%I64d%d",&n,&a,&b);
        sum=b+a*2;
        ans=a*2+b;
        for(int i=1;i<=n;i++)
            scanf("%d",s+i);
            for(int i=1;i<n;i++)
                s[i]=s[i+1]-s[i];
                for(int i=1;i<n;i++)
                {
                    if(s[i]*b>=ans)
                        sum+=ans;
                    else sum+=s[i]*b;
                }
                printf("Case #%d: %I64d\n",Case++,sum);

    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u013712847/article/details/40450993


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  4. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的