首页 > ACM题库 > HDU-杭电 > HDU 4724-If You Know This,You Must Have NO GF-贪心-[解题报告]HOJ
2015
09-17

HDU 4724-If You Know This,You Must Have NO GF-贪心-[解题报告]HOJ

If You Know This,You Must Have NO GF

问题描述 :

In software development, Make is a utility that automatically builds executable programs and libraries from source code by reading files called makefiles which specify how to derive the target program. Though integrated development environments and language-specific compiler features can also be used to manage a build process, Make remains widely used, especially in Unix.
Now let’s have a look at the grammar of makefile. Please note that in this problem, we have simplified the problem a lot, so read carefully, especially when you are familiar with such things. In this problem, makefile contains three kinds of statements:

1. Target: [component ...]

This is a statement to define a target. To build "Target", you have to generate all the files in [component ...] at first. Here is an example:
a.o: a.cc b.cc
Which means if you want to generate file a.o, you have to make sure that there are already file a.cc and b.cc in the directory.
Each component(including the target itself) will be a string which is a legal file’s name, as "aaa" or "aaa.bbb". They will be separated by some spaces.
A legal file’s name will only contain letters (upper case and lower case), numbers and only contain one dot (.).
There won’t be two Targets sharing a same file name. Also relations between files won’t form a circle.

2. Commands

This is a command shows how to build the Target, usually written after statement 1. Here is an example:

    g++ a.o b.o -o main

Note this kind of commands will have *FOUR SPACES* at the front of the line.
There maybe two or more commands after statement 1.

3. Comments

Comments begin with character ‘#’, which should be ignored. Note that ‘#’ can appear in any place in the line, and all character after ‘#’ in the line shall be ignored. Here is an example:
a.o: a.cc b.cc #hello world!
This should be regarded as
a.o: a.cc b.cc

Sometimes you may find a statement is too long to be written in a single line. You can add a ‘\’ at the end of the line, indicating that there are still part of statement at the next line. Here is an example:

main: a.o\
b.o
g++ a.o b.o -o main

This equals to the statement

main: a.o b.o
g++ a.o b.o -o main

Notice that ‘\’ will only appear at end of the line and not appear in comments.
Now this is all a makefile will have.
You have a makefile, and you will execute Q "make" commands one by one. There are already some files in the directory.
The make command is like this:
make Target
Which will try to generate a file named "Target".
If there are no such "Target" defined in the makefile, or it cannot be built since lack of files. This command will not get executed.
Your task is, after executing each command, how many new files will appear in the directory?

输入:

The first line has a number T (T <= 10) , indicating the number of test cases.
Then some lines come, indicating the content of makefile. A string "====" indicating the end of makefile. each line is no longer than 1000 characters. the size of makefile will not exceed 1MB.
There are at most 500 target in the Makefile.
Then comes a single line with a number N(N <= 500). Which is the number of files that are already in the directory.
Then come N lines each with a file name.
Then comes a single line with a number Q(Q <= 500). Which is the number of command you are going to execute.
Then come Q lines each with a command, within the pattern "make Target".

输出:

The first line has a number T (T <= 10) , indicating the number of test cases.
Then some lines come, indicating the content of makefile. A string "====" indicating the end of makefile. each line is no longer than 1000 characters. the size of makefile will not exceed 1MB.
There are at most 500 target in the Makefile.
Then comes a single line with a number N(N <= 500). Which is the number of files that are already in the directory.
Then come N lines each with a file name.
Then comes a single line with a number Q(Q <= 500). Which is the number of command you are going to execute.
Then come Q lines each with a command, within the pattern "make Target".

样例输入:

[pre]2
main: a.o b.o
    g++ a.o b.o -o main
a.o: a.cc
    g++ a.cc -o a.o -c
b.o: b.cc
    g++ b.cc -o b.o -c
main2: a.o c.o
    g++ a.o c.o -o main2
====
3
a.cc
b.cc
c.o
2
make main
make main2

main: a.o b.o
    g++ a.o b.o -o main
a.o: a.cc
    g++ a.cc -o a.o -c
b.o: b.cc
    g++ b.cc -o b.o -c
main2: a.o c.o
    g++ a.o c.o -o main2
====
2
a.cc
b.cc
2
make main
make main2[/pre]

样例输出:

Case #1:
3
1

Case #2:
3
0

题目看起来很难,其实很简单。。。。

根据题意可知,如果想连到最多的三角形,肯定是每个点都要跟其他的点相连。

然后就贪心当前连接情况下,哪一种连接方式用掉的线段最短,然后算出总和即可。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
using namespace std;
#define maxn 110000
#define INF 99999999
double c[maxn];
double d[maxn];
double a,b;
int main()
{
    int T,cas,n,m;
    cas=0;
    scanf("%d",&T);
    while(T--)
    {
        cas++;
        scanf("%lf%lf",&a,&b);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%lf",&c[i]);
        for(int i=1;i<=m;i++)scanf("%lf",&d[i]);
        double ans=0.0;
        int stx,sty;
        stx=sty=1;
        double st=(a-b)*(a-b);
        ans+=sqrt((c[1]-d[1])*(c[1]-d[1])+st);
        while(1)
        {
            double x,y;
            x=y=1000000000.0;
            int leap=0;
            if(stx<n)
            {
                x=sqrt((c[stx+1]-d[sty])*(c[stx+1]-d[sty])+st);
                leap=1;
            }
            if(sty<m)
            {
                y=sqrt((c[stx]-d[sty+1])*(c[stx]-d[sty+1])+st);
                leap=1;
            }
            if(!leap)break;
            if(x<y)
            {
                stx++;
                ans+=x;
            }
            else
            {
                sty++;
                ans+=y;
            }
        }
        printf("Case #%d: %.2f\n",cas,ans);
    }
    return 0;
}











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

参考:http://blog.csdn.net/rowanhaoa/article/details/37057279