HDU 4723 How Long Do You Have to Draw(贪心)

Description:

There are two horizontal lines on the XoY plane. One is y1 = a, the other is y2 = b(a < b). On line y1, there are N points from left to right, the x-coordinate of which are x = c1, c2, … , cN (c1 < c2 < … < cN) respectively. And there are also M points on line y2 from left to right. The x-coordinate of the M points are x = d1, d2, … dM (d1 < d2 < … < dM) respectively.
Now you can draw segments between the points on y1 and y2 by some segments. Each segment should exactly connect one point on y1 with one point on y2.
The segments cannot cross with each other. By doing so, these segments, along with y1 and y2, can form some triangles, which have positive areas and have no segments inside them.
The problem is, to get as much triangles as possible, what is the minimum sum of the length of these segments you draw?

Input:

The first line has a number T (T <= 20) , indicating the number of test cases.
For each test case, first line has two numbers a and b (0 <= a, b <= 104), which is the position of y1 and y2.
The second line has two numbers N and M (1 <= N, M <= 105), which is the number of points on y1 and y2.
The third line has N numbers c1, c2, … , cN(0 <= ci < ci+1 <= 106), which is the x-coordinate of the N points on line y1.
The fourth line has M numbers d1, d2, … , dM(0 <= di < di+1 <= 106), which is the x-coordinate of the M points on line y2.

Output:

For test case X, output "Case #X: " first, then output one number, rounded to 0.01, as the minimum total length of the segments you draw.

Sample Input:

1
0 1
2 3
1 3
0 2 4

Sample Output:

Case #1: 5.66

题目链接

题目给出两条平行x轴的直线和两条线上分别的若干点，连接两线之间点为线段，让所有线段无交点，使线段组成的三角形尽可能的多，求最小线段和。题目解法使用贪心，从左至右依次连接线段，连接方法为：先连接两条线上最左边的两点，然后依次比较第一条线上第一个未连接点到第二条线上最后一个已连接点的距离和第二条线上第一个未连接点到第一条线上最后一个已连接点的距离选择短的那条线段连接，直到有一条线上所有点全部连接完毕，再循环那条点没有全部连接完的直线，把剩下的点全部与另一条直线上最后一个点相连成线段。
这道题目用cin&&cout会超时(即使关闭同步流)。

AC代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const double eps = 1e-5;
const double e = 2.718281828459;

int t;
int a, b;
double a_b_dis;
int n, m;
int c_cnt, d_cnt;
double c[maxn], d[maxn];
double ans;

void Get_information() {
    //cin >> a >> b >> n >> m;
    scanf("%d%d%d%d", &a, &b, &n, &m);
    a_b_dis = pow(a - b, 2);
    for (int i = 0; i < n; ++i) {
        scanf("%lf", &c[i]);
        //cin >> c[i];
    }
    for (int i = 0; i < m; ++i) {
        //cin >> d[i];
        scanf("%lf", &d[i]);
    }
}

double Cal_dis(double x1, double x2) {
    return sqrt(pow(x1 - x2, 2) + a_b_dis);
}

void Solve() {
    ans += Cal_dis(c[0], d[0]);
    c_cnt = 1; d_cnt = 1;
    while (c_cnt < n && d_cnt < m) {
        double c_judge_temp = Cal_dis(c[c_cnt], d[d_cnt - 1]);
        double d_judge_temp = Cal_dis(c[c_cnt - 1], d[d_cnt]);
        if (c_judge_temp < d_judge_temp) {
            ans += c_judge_temp;
            c_cnt++;
        }
        else {
            ans += d_judge_temp;
            d_cnt++;
        }
    }
    while (c_cnt < n) {
        ans += Cal_dis(c[c_cnt], d[d_cnt - 1]);
        c_cnt++;
    }
    while (d_cnt < m) {
        ans += Cal_dis(c[c_cnt - 1], d[d_cnt]);
        d_cnt++;
    }
}

int main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cin >> t;
    scanf("%d", &t);
    for (int Case = 1; Case <= t; ++Case) {
        ans = 0;
        Get_information();
        if (n == 1 && m == 1) {
            printf("Case #%d: %.2lf\n", Case, ans);
            //cout << "Case #" << Case << ": ";
            //cout << setiosflags(ios::fixed) << setprecision(2) << ans << endl;
            continue;
        }
        if (!n || !m) {
            printf("Case #%d: %.2lf\n", Case, ans);
            //cout << "Case #" << Case << ": ";
            //cout << setiosflags(ios::fixed) << setprecision(2) << ans << endl;
            continue;
        }
        Solve();
        //cout << "Case #" << Case << ": ";
        //cout << setiosflags(ios::fixed) << setprecision(2) << ans << endl;
        printf("Case #%d: %.2lf\n", Case, ans);
    }
    return 0;
}