1 篇博文 含有标签「algorithm」

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n-- > 0) {
        int len;
        cin >> len;
        string a = "";
        string b = "";
        for (int i = 0; i < len; i += 1) {
            char tempA, tempB;
            cin >> tempA >> tempB;
            a += tempA;
            b += tempB;
        }
        int carry = 0;
        for (int i = len - 1; i >= 0; i -= 1) {
            int n1 = a[i] - '0';
            int n2 = b[i] - '0';
            int temp = n1 + n2 + carry;
            carry = temp > 9 ? 1 : 0;
            temp -= carry * 10;
            a[i] = '0' + temp;
        }
        cout << a << endl;
        if (n > 0) {
            cout << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

struct Point
{
    int root;
    double x;
    double y;
};

struct Line
{
    int indexStart; // smallest
    int indexEnd;   // greatest
    double distance;
};

bool compareByLength(const Line &a, const Line &b)
{
    return a.distance > b.distance;
}

int main()
{
    int n;
    cin >> n;
    while (true)
    {
        int len;
        cin >> len;

        Point points[len];
        vector<Line> lines;

        for (int i = 0; i < len; i += 1)
        {
            Point point;
            cin >> point.x >> point.y;
            point.root = i;
            points[i] = point;
        }

        for (int i = 0; i < len; i += 1)
        {
            for (int j = i + 1; j < len; j += 1)
            {
                Line line;
                line.indexStart = i;
                line.indexEnd = j;
                line.distance = sqrt(pow(abs(points[i].x - points[j].x), 2) + pow(abs(points[i].y - points[j].y), 2));
                lines.push_back(line);
            }
        }

        sort(lines.begin(), lines.end(), compareByLength);

        double ans = 0;
        while (true)
        {
            Line line = lines.back();
            lines.pop_back();

            if (points[line.indexStart].root == points[line.indexEnd].root)
                continue;
            ans += line.distance;

            int root2 = points[line.indexEnd].root;
            for (int i = 0; i < len; i++)
            {
                if (points[i].root == root2)
                {
                    points[i].root = points[line.indexStart].root;
                }
            }
            bool done = true;
            for (int i = 1; i < len; i++)
            {
                if (points[0].root != points[i].root)
                {
                    done = false;
                    break;
                }
            }
            if (done)
            {
                break;
            }
        }

        cout << round(ans * 100) / 100 << endl;
        n -= 1;
        if (n == 0) {
            break;
        }
        cout << endl;
    }
    return 0;
}