imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:26Z

New page

=== 그리디로 ===
// 10201 - Adventures in Moving: Part IV
#include <iostream>
using namespace std;

#define MAX_OIL 200
#define MAX_SIZE 103
#define MAX_NUM 1000000000

typedef struct
{
int length;
int price;
}Station;

static int totalLength; /* 워털루에서 대도시까지의 거리 */
static int numStation; /* 주유소 수 */
static Station station[MAX_SIZE]; /* 주유소 정보 */

inline
int getDistance(int i)
{
return station[i].length - station[i-1].length;
}

void input()
{
cin >> totalLength;
totalLength += 100;
cin.get();
numStation = 1;
station[numStation].length = 0;
station[numStation].price = 0;
while (cin.peek() != EOF && cin.peek() != '\n')
{
numStation++;
cin >> station[numStation].length >> station[numStation].price;
cin.get();
}
cin.get();
numStation++;
station[numStation].length = totalLength;
station[numStation].price = 0;
}

void process()
{
int maxmin, maxminprice , now = 1, tank = 100, go = 100, search = 2, cost = 0;

while(now != numStation)
{
maxmin = 0;
maxminprice = 1000000;
while(station[now].length + go >= station[search].length)
{
// 서치의 가격이 작거나 같을때
if(station[now].price > station[search].price)
{
if(station[search].length - station[now].length >= tank)
{
cost += (station[search].length - station[now].length - tank)*station[now].price;
tank = 0;
}
else
tank = tank - station[search].length + station[now].length;
now = search++;
maxmin = 0;
break;
}
// 서치의 가격이 클때
else
{
if(maxminprice > station[search].price)
{
maxmin = search;
maxminprice = station[search].price;
}
search++;
}
}
// 작은게 없을때
if(now + 1 == search && station[now].length + go < station[search].length)
{
cout << "Impossible\n";
return;
}
if(maxmin)
{
if(station[maxmin].length - station[now].length >= tank)
{
cost += (200 - tank)*station[now].price;
tank = go - station[maxmin].length + station[now].length;
}
else
tank = tank - station[maxmin].length + station[now].length;

now = maxmin;
search = now +1;
}
go = 200;
}

cout << cost << endl;
}

int main()
{
int numCase;
cin >> numCase;
cin.get(), cin.get();
for (int i = 0; i < numCase; i++)
{
input();
process();
if (i != numCase - 1)
cout << endl;
}
return 0;
}

AdventuresInMoving:PartIV/김상섭 - Revision history

imported>Unknown at 05:22, 7 February 2021