若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1105: Problem A: Bridge

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,290

题目描述

Problem A: Bridge
n people wish to cross a bridge at night. A group of at most two people may cross at any time, and each group must have a flashlight. Only one flashlight is available among the n people, so some sort of shuttle arrangement must be arranged in order to return the flashlight so that more people may cross.
Each person has a different crossing speed; the speed of a group is determined by the speed of the slower member. Your job is to determine a strategy that gets all n people across the bridge in the minimum time.
The first line of input contains n, followed by n lines giving the crossing times for each of the people. There are not more than 1000 people and nobody takes more than 100 seconds to cross the bridge.
The first line of output must contain the total number of seconds required for all n people to cross the bridge. The following lines give a strategy for achieving this time. Each line contains either one or two integers, indicating which person or people form the next group to cross. (Each person is indicated by the crossing time specified in the input. Although many people may have the same crossing time the ambiguity is of no consequence.) Note that the crossings alternate directions, as it is necessary to return the flashlight so that more may cross. If more than one strategy yields the minimal time, any one will do.

输入

暂无

输出

暂无

样例输入

4
1
2
5
10

样例输出

17
1 2
1
5 10
2
1 2

参考代码

#include <stdio.h>
struct e 
{
    long x,y,x1,y1;
}
;
long x[101], y[101];
struct e up[101], dn[101];
int n, nup, ndn;
long top,top1,top2,bot,bot1,bot2;
long long area;
cmp (struct e *a, struct e *b) 
{
    if (b->y > a->y) return 1;
    if (b->y < a->y) return -1;
    return b->y1 - a->y1;
}
main() 
{
    int i,j,k;
    for (n=0;2 == scanf("%d%d",&x[n],&y[n]);n++);
    x[n] = x[0];
    y[n] = y[0];
    for (i=0;i<n;i++) 
    {
        if (x[i] < x[i+1]) 
        {
            if (y[i] < y[i+1]) 
            {
                up[nup].x = x[i];
                up[nup].y = y[i];
                up[nup].x1 = x[i+1];
                up[nup++].y1 = y[i+1];
            } else 
            {
                dn[ndn].x = x[i];
                dn[ndn].y = y[i];
                dn[ndn].x1 = x[i+1];
                dn[ndn++].y1 = y[i+1];
            }
        } else if (x[i+1] < x[i]) 
        {
            if (y[i+1] < y[i]) 
            {
                up[nup].x = x[i+1];
                up[nup].y = y[i+1];
                up[nup].x1 = x[i];
                up[nup++].y1 = y[i];
            } else 
            {
                dn[ndn].x = x[i+1];
                dn[ndn].y = y[i+1];
                dn[ndn].x1 = x[i];
                dn[ndn++].y1 = y[i];
            }
        }
    }
    qsort(up,nup,sizeof(struct e),cmp);
    qsort(dn,ndn,sizeof(struct e),cmp);
    up[nup].x = 0;
    up[nup].y = -1;
    up[nup].x1 = 1000000;
    up[nup++].y1 = -1;
    dn[ndn].x = 0;
    dn[ndn].y = -1;
    dn[ndn].x1 = 1000000;
    dn[ndn++].y1 = -1;
    for (i=0;i<1000000;i++) 
    {
        for (j=0;up[j].x > i || up[j].x1 <= i;j++);
        for (k=0;dn[k].x > i || dn[k].x1 <= i;k++);
        while(1) 
        {
            bot1 = up[j].y+((long long)i-up[j].x)*(up[j].y1-up[j].y)/(up[j].x1-up[j].x);
            bot2 = dn[k].y+((long long)(i+1-dn[k].x)*(dn[k].y1-dn[k].y)-(dn[k].x1-dn[k].x)+1)/(dn[k].x1-dn[k].x);
            if (bot1 > bot2) 
            {
                bot = bot1;
                for (j++;up[j].x > i || up[j].x1 <= i;j++);
            } else if (bot2 > bot1) 
            {
                bot = bot2;
                for (k++;dn[k].x > i || dn[k].x1 <= i;k++);
            } else break;
            top1 = up[j].y+((long long)(i+1-up[j].x)*(up[j].y1-up[j].y)+(up[j].x1-up[j].x)-1)/(up[j].x1-up[j].x);
            top2 = dn[k].y+((long long)i-dn[k].x)*(dn[k].y1-dn[k].y)/(dn[k].x1-dn[k].x);
            if (top1 > top2) 
            {
                top = top1;
                for (j++;up[j].x > i || up[j].x1 <= i;j++);
            } else if (k < ndn && top2 > top1) 
            {
                top = top2;
                for (k++;dn[k].x > i || dn[k].x1 <= i;k++);
            } else 
            {
                fprintf(stderr,"oops!n;");
                *(char *)0 = 1;
            }
            if (bot > top) area = area + bot - top;
        }
    }
    printf("%lldn",area);
}

解析

暂无

hustoj

发表评论 取消回复

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

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip 原站点 Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist