题意:
给出两种操作:ADD(x),将x添加到有序列表中;GET()返回全局迭代器所指的值,其中迭代器在GET操作后会自添加1
题解:
刚开始直接手打链表模拟,结果超时。这时应使用另外一种方法:使用大顶堆和小顶堆。
其中,对于序列S[1..n],及表示迭代器位置的index,大顶堆维护排序后的S[1..index-1],小顶堆维护
排序后的S[index..n],例如S[1..n]金沙城中心赌场 , = 1,2,3,4,5,6,7,index =
4,则大顶堆为{1,2,3},小顶堆为{4,5,6,7}
为什么要这样维护呢?因为当小堆最小的元素都大于大堆最大的元素时,那么序列中排第n个就是小堆最小的数了。
我们假设第k趟GET()后,有以下情景(GET后k自动加1):
大顶堆:S[1..k],堆顶元素为S[k],小顶堆:S[k+1,n],堆顶元素为S[k+1],然后每当添加一个元素newE时,先添加到大顶堆中,这时如果出现大顶堆数大于小顶堆的数时,理应交换。
代码: #include <queue>
#include <stdio.h>
using namespace std;

Intersecting
Lines
简而言之就是求两条线的关系,平行?重合?相交?如果相交的话求出交叉点。
方式有很多种,有用向量的,有用斜率的。其实这算是个水题,只不过需要考虑点边界情况。

int m,n;
int sequence[30005];

代码如下:

struct cmp1
{
    bool operator()(const int a,const int b)
    {
        return a>b;
    }
};
struct cmp2
{
    bool operator()(const int a,const int b)
    {
        return a<b;
    }
};

#include <math.h>
#include <stdio.h>

struct Point {
    double x;
    double y;

    bool operator==(const Point &other) const {
        return (x == other.x && y == other.y);
    }
};

/**
 * 假设直线方程为 y = kx + n
 **/
struct Line {
    struct Point a;
    struct Point b;

    bool isVertical() {
        return a.x == b.x;
    }

    // 这里需要注意直线情况
    double getSlope() {
        return (b.y - a.y)/(b.x - a.x);
    }

    double getSuffix() {
        return a.y - getSlope()*a.x;
    }
};

/**
 * 是否平行
 **/
bool isParallel(struct Line line1, struct Line line2) {
    double dxLine1 = line1.a.x - line1.b.x;
    double dyline1 = line1.a.y - line1.b.y;

    double dxLine2 = line2.a.x - line2.b.x;
    double dyline2 = line2.a.y - line2.b.y;

    if (0 == dxLine1) {
        return (0 == dxLine2);
    }

    return (dyline2*dxLine1 == dyline1*dxLine2);
}

/**
 * 是否是同一条直线
 **/
bool isInLine(struct Line line1, struct Line line2) {

    // 先计算是否平行,不平行的线一定不会是同一条直线
    if(!isParallel(line1, line2)) {
        return false;
    }

    // 平行且过同一个点,则肯定是同一条直线
    if (line1.a == line2.a) {
        return true;
    }

    // 否则以 line1.a line2.a 构造第三条线,看是否与 line1 平行
    struct Line lineTmp = {line1.a, line2.a};
    return isParallel(line1, lineTmp);
}

struct Point intersectPoint(struct Line line1, struct Line line2) {
    struct Point point = {0, 0};
    if (line1.isVertical()) {
        point.x = line1.a.x;
        point.y = line2.getSlope()*point.x + line2.getSuffix();
    } else if (line2.isVertical()) {
        point.x = line2.a.x;
        point.y = line1.getSlope()*point.x + line1.getSuffix();
    } else {
        point.x = (line2.getSuffix() - line1.getSuffix())/(line1.getSlope() - line2.getSlope());
        point.y = line1.getSlope()*point.x + line1.getSuffix();
    }
    return point;
}

int main(int argc, const char * argv[]) {

    int turn = 0;
    scanf("%d", &turn);

    printf("INTERSECTING LINES OUTPUT\n");

    for (int i = 0; i < turn; i++) {
        struct Line line1, line2;
        scanf("%lf %lf %lf %lf", &line1.a.x, &line1.a.y, &line1.b.x, &line1.b.y);
        scanf("%lf %lf %lf %lf", &line2.a.x, &line2.a.y, &line2.b.x, &line2.b.y);

        if (isInLine(line1, line2)) {
            printf("LINE\n");
            continue;
        }

        if (isParallel(line1, line2)) {
            printf("NONE\n");
            continue;
        }

        struct Point point = intersectPoint(line1, line2);
        printf("POINT %.2lf %.2lf\n", point.x, point.y);
    }
    printf("END OF OUTPUT");
}

void Test()
{
    priority_queue<int,vector<int>,cmp1>q1;//小堆
    priority_queue<int,vector<int>,cmp2>q2;//大堆

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图