poj3190

maksyuki 发表于 oj 分类，标签: 基础算法-贪心, 数据结构-队列\双端\单调\优先

09 10月 2015

Stall Reservations

Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.

Help FJ by determining:

The minimum number of stalls required in the barn so that each cow can have her private milking period
An assignment of cows to these stalls over time

Many answers are correct for each test dataset; a program will grade your answer.

Input

Line 1: A single integer, N

Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated integers.

Output

Line 1: The minimum number of stalls the barn must have.

Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.

Sample Input

5
1 10
2 4
3 6
5 8
4 7

Sample Output

Hint

Explanation of the sample:

Here's a graphical schedule for this output:

Time 1 2 3 4 5 6 7 8 9 10
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

Other outputs using the same number of stalls are possible.

Source

USACO 2006 February Silver

题目类型：贪心+优先队列

算法分析：为了使得stall数最少，需要将能够串行先后执行的时间区间合并在一个stall中执行。首先将区间按照左端点递增排序，然后依次比较区间的左端点和前面设置好的stall的“容量”的最小值。若区间左端点相比较小，则表示存在一个时间段是重合的，需要再开一个stall，否则更新此时stall的“容量”，类似于向若干个背包分发物品。这里使用优先队列来动态维护最小值。注意比较条件一定是大于！！！注意最后输出是按照输入顺序的区间来输出！！！

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 5e4 + 66;

struct node{ int x, y, id;};

struct point
{
    int x, y;
    point (int xx, int yy) : x (xx), y (yy) {}
    point () {}
};

bool operator < (const node&a, const node&b) {return a.x < b.x;}
bool operator < (const point&a, const point&b) {return a.x > b.x;}

node aa[maxn];
priority_queue <point> qu;
int out[maxn];

int main()
{
//    CFF;
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf (" %d %d", &aa[i].x, &aa[i].y);
            aa[i].id = i;
        }

        sort (aa + 1, aa + 1 + n);
        while (!qu.empty ()) qu.pop ();

        qu.push (point (0, 1));
        int len = 2;
        for (int i = 1; i <= n; i++)
        {
            point minval = qu.top ();
            if (aa[i].x > minval.x)
            {
                out[aa[i].id] = minval.y;
                qu.pop ();
                minval.x = aa[i].y;
                qu.push (minval);
            }

            else
            {
                out[aa[i].id] = len;
                qu.push (point (aa[i].y, len++));
            }
        }
        printf ("%d\n", len - 1);
        for (int i = 1; i <= n; i++)
            printf ("%d\n", out[i]);
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5e4 + 66;

struct node{ int x, y, id;};

struct point

{

int x, y;

point (int xx, int yy) : x (xx), y (yy) {}

point () {}

};

bool operator < (const node&a, const node&b) {return a.x < b.x;}

bool operator < (const point&a, const point&b) {return a.x > b.x;}

node aa[maxn];

priority_queue <point> qu;

int out[maxn];

int main()

{

// CFF;

int n;

while (scanf ("%d", &n) != EOF)

{

for (int i = 1; i <= n; i++)

{

scanf (" %d %d", &aa[i].x, &aa[i].y);

aa[i].id = i;

}

sort (aa + 1, aa + 1 + n);

while (!qu.empty ()) qu.pop ();

qu.push (point (0, 1));

int len = 2;

for (int i = 1; i <= n; i++)

{

point minval = qu.top ();

if (aa[i].x > minval.x)

{

out[aa[i].id] = minval.y;

qu.pop ();

minval.x = aa[i].y;

qu.push (minval);

}

else

{

out[aa[i].id] = len;

qu.push (point (aa[i].y, len++));

}

printf ("%d\n", len - 1);

for (int i = 1; i <= n; i++)

printf ("%d\n", out[i]);

}

return 0;

}

poj2376

maksyuki 发表于 oj 分类，标签: 基础算法-排序, 基础算法-贪心

07 10月 2015

Cleaning Shifts

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.

Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.

Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.

Input

* Line 1: Two space-separated integers: N and T

* Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.

Output

* Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.

Sample Input

3 10
1 7
3 6
6 10

Sample Output

Hint

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

INPUT DETAILS:

There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.

OUTPUT DETAILS:

By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.

Source

USACO 2004 December Silver

题目类型：排序+贪心

算法分析：首先按照开始时间递增排序，然后按照结束时间递增排序，由贪心策略可知一定要选择第一个区间，且如果这个区间的左端点大于1，则直接输出-1，否则每次向右找满足x < tt.y + 1的最大右端点的值。然后看最后是否能够将t这个位置覆盖住

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

struct node{int x, y;};

node aa[maxn];

bool operator < (const node &a, const node &b)
{
    if (a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}

int main()
{
//    CFF;
    int n, t;
    while (scanf ("%d%d", &n, &t) != EOF)
    {
        for (int i = 1; i <= n; i++)
            scanf ("%d%d", &aa[i].x, &aa[i].y);

        sort (aa + 1, aa + 1 + n);
        int pos = 0, tmax, res = 0, i = 1;
        while (i <= n && pos < t)
        {
            res++;
            tmax = pos;
            if (aa[i].x > pos + 1)
            {
                puts ("-1");
                return 0;
            }

            while (i <= n && aa[i].x <= pos + 1)
            {
                tmax = max (tmax, aa[i].y);
                i++;
            }
            pos = tmax;
        }

        if (pos >= t)
            printf ("%d\n", res);

        else
            puts ("-1");

    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

struct node{int x, y;};

node aa[maxn];

bool operator < (const node &a, const node &b)

{

if (a.x != b.x) return a.x < b.x;

else return a.y < b.y;

}

int main()

{

// CFF;

int n, t;

while (scanf ("%d%d", &n, &t) != EOF)

{

for (int i = 1; i <= n; i++)

scanf ("%d%d", &aa[i].x, &aa[i].y);

sort (aa + 1, aa + 1 + n);

int pos = 0, tmax, res = 0, i = 1;

while (i <= n && pos < t)

{

res++;

tmax = pos;

if (aa[i].x > pos + 1)

{

puts ("-1");

return 0;

}

while (i <= n && aa[i].x <= pos + 1)

{

tmax = max (tmax, aa[i].y);

i++;

}

pos = tmax;

}

if (pos >= t)

printf ("%d\n", res);

else

puts ("-1");

}

return 0;

}

Codeforces Round #323(Div.2) (2/5) (Div.1) (0/5)

maksyuki 发表于比赛分类，标签: 比赛-codeforces

05 10月 2015

A Asphalting Roads

City X consists of n vertical and n horizontal infinite roads, forming n × n intersections. Roads (both vertical and horizontal) are numbered from 1 to n, and the intersections 阅读全文 »

BestCoder Round #58(Div.2) (4/4) (Div.1) (3/4)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

03 10月 2015

A Card Game

Problem Description

Soda and Beta are good friends. They are going to play a card game today. Soda has n cards with number a1,a2,...,an 阅读全文 »

poj3050

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

02 10月 2015

Hopscotch

The cows play the child's game of hopscotch in a non-traditional way. Instead of a linear set of numbered boxes into which to hop, the cows create a 5x5 rectilinear grid of digits parallel to the x and y axes.

They then adroitly hop onto any digit in the grid and hop forward, backward, right, or left (never diagonally) to another digit in the grid. They hop again (same rules) to a digit (potentially a digit already visited).

With a total of five intra-grid hops, their hops create a six-digit integer (which might have leading zeroes like 000201).

Determine the count of the number of distinct integers that can be created in this manner.

Input

* Lines 1..5: The grid, five integers per line

Output

* Line 1: The number of distinct integers that can be constructed

Sample Input

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1

Sample Output

Hint

OUTPUT DETAILS:
111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, and 212121 can be constructed. No other values are possible.

Source

USACO 2005 November Bronze

题目类型：DFS

算法分析：直接搜索6步并判断，注意使用string会TLE!!!

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 5e4 + 66;

const int dx[] = {0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};

int aa[10][10], res;
set <int> se;

void dfs (int x, int y, int t, int cur)
{
    if (t == 6)
    {
        if (se.count (cur) == 0)
        {
            res++;
            se.insert (cur);
        }
        return ;
    }

    for (int i = 0; i < 4; i++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx >= 1 && tx <= 5 && ty >= 1 && ty <= 5)
            dfs (tx, ty, t + 1, cur * 10 + aa[tx][ty]);
    }
}


int main()
{
//    CFF;
    while (scanf ("%d", &aa[1][1]) != EOF)
    {
        for (int i = 1; i <= 5; i++)
            for (int j = 1; j <= 5; j++)
            {
                if (i == 1 && j == 1)
                    continue;

                scanf ("%d", &aa[i][j]);
            }

        se.clear ();
        res = 0;
        for (int i = 1; i <= 5; i++)
            for (int j = 1; j <= 5; j++)
            {
                dfs (i, j, 0, 0);
            }

        printf ("%d\n", res);
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5e4 + 66;

const int dx[] = {0, -1, 0, 1};

const int dy[] = {-1, 0, 1, 0};

int aa[10][10], res;

set <int> se;

void dfs (int x, int y, int t, int cur)

{

if (t == 6)

{

if (se.count (cur) == 0)

{

res++;

se.insert (cur);

}

return ;

}

for (int i = 0; i < 4; i++)

{

int tx = x + dx[i], ty = y + dy[i];

if (tx >= 1 && tx <= 5 && ty >= 1 && ty <= 5)

dfs (tx, ty, t + 1, cur * 10 + aa[tx][ty]);

}

int main()

{

// CFF;

while (scanf ("%d", &aa[1][1]) != EOF)

{

for (int i = 1; i <= 5; i++)

for (int j = 1; j <= 5; j++)

{

if (i == 1 && j == 1)

continue;

scanf ("%d", &aa[i][j]);

}

se.clear ();

res = 0;

for (int i = 1; i <= 5; i++)

for (int j = 1; j <= 5; j++)

{

dfs (i, j, 0, 0);

}

printf ("%d\n", res);

}

return 0;

}

poj3669

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

01 10月 2015

Meteor Shower

Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hit. Anxious for her safety, she vows to find her way to a safe location (one that is never destroyed by a meteor) . She is currently grazing at the origin in the coordinate plane and wants to move to a new, safer location while avoiding being destroyed by meteors along her way.

The reports say that M meteors (1 ≤ M ≤ 50,000) will strike, with meteor i will striking point (X_i, Y_i) (0 ≤ X_i≤ 300; 0 ≤ Y_i≤ 300) at time T_i (0 ≤ T_i ≤ 1,000). Each meteor destroys the point that it strikes and also the four rectilinearly adjacent lattice points.

Bessie leaves the origin at time 0 and can travel in the first quadrant and parallel to the axes at the rate of one distance unit per second to any of the (often 4) adjacent rectilinear points that are not yet destroyed by a meteor. She cannot be located on a point at any time greater than or equal to the time it is destroyed).

Determine the minimum time it takes Bessie to get to a safe place.

Input

* Line 1: A single integer: M
* Lines 2..M+1: Line i+1 contains three space-separated integers: X_i, Y_i, and T_i

Output

* Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.

Sample Input

4
0 0 2
2 1 2
1 1 2
0 3 5

Sample Output

Source

USACO 2008 February Silver

题目类型：BFS

算法分析：先将每个会被流星雨摧毁的点标记下来，表示这不是终止节点。然后按照流星雨袭击的时间递增排序，每次扩展状态时，要额外更新被摧毁的节点的情况

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 5e4 + 66;

const int dx[] = {0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};

struct node
{
    int x, y, t;
    node (int xx, int yy, int tt) : x (xx), y (yy), t (tt) {}
    node () {}
};

bool operator < (const node &a, const node &b) {return a.t < b.t;}

int pp;
node aa[maxn];
bool vis[366][366], vvis[366][366];

inline bool Ok (int x, int y)
{
    if (x >= 0 && y >= 0 && !vis[x][y])
        return true;

    return false;
}

void PP (int t)
{
    while (aa[pp].t <= t)
    {
        vis[aa[pp].x][aa[pp].y] = true;
        for (int i = 0; i < 4; i++)
        {
            int tx = aa[pp].x + dx[i], ty = aa[pp].y + dy[i];
            if (tx >= 0 && ty >= 0)
                vis[tx][ty] = true;
        }
        pp++;
    }
}


int bfs (int x, int y, int t)
{
    memset (vis, false, sizeof (vis));
    queue <node> qu;
    qu.push (node (x, y, t));
    vis[x][y] = true;
    pp = 1;
    PP (0);
    while (!qu.empty ())
    {
        node temp = qu.front ();
        qu.pop ();

        PP (temp.t+1);

        if (!vvis[temp.x][temp.y])
        {
            return temp.t;
        }

        for (int i = 0; i < 4; i++)
        {
            int tx = temp.x + dx[i], ty = temp.y + dy[i];
            if (Ok (tx, ty))
            {
                qu.push (node (tx, ty, temp.t + 1));
                vis[tx][ty] = true;
            }
        }
    }
    return -1;
}


int main()
{
//    CFF;
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        memset (vvis, false, sizeof (vvis));
        for (int i = 1; i <= n; i++)
        {
            scanf ("%d%d%d", &aa[i].x, &aa[i].y, &aa[i].t);
            vvis[aa[i].x][aa[i].y] = true;
            for (int j = 0; j < 4; j++)
            {
                int tx = aa[i].x + dx[j], ty = aa[i].y + dy[j];
                if (tx >= 0 && ty >= 0)
                    vvis[tx][ty] = true;
            }
        }
        sort (aa + 1, aa + 1 + n);
        printf ("%d\n", bfs (0, 0, 0));
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5e4 + 66;

const int dx[] = {0, -1, 0, 1};

const int dy[] = {-1, 0, 1, 0};

struct node

{

int x, y, t;

node (int xx, int yy, int tt) : x (xx), y (yy), t (tt) {}

node () {}

};

bool operator < (const node &a, const node &b) {return a.t < b.t;}

int pp;

node aa[maxn];

bool vis[366][366], vvis[366][366];

inline bool Ok (int x, int y)

{

if (x >= 0 && y >= 0 && !vis[x][y])

return true;

return false;

}

void PP (int t)

{

while (aa[pp].t <= t)

{

vis[aa[pp].x][aa[pp].y] = true;

for (int i = 0; i < 4; i++)

{

int tx = aa[pp].x + dx[i], ty = aa[pp].y + dy[i];

if (tx >= 0 && ty >= 0)

vis[tx][ty] = true;

}

pp++;

}

int bfs (int x, int y, int t)

{

memset (vis, false, sizeof (vis));

queue <node> qu;

qu.push (node (x, y, t));

vis[x][y] = true;

pp = 1;

PP (0);

while (!qu.empty ())

{

node temp = qu.front ();

qu.pop ();

PP (temp.t+1);

if (!vvis[temp.x][temp.y])

{

return temp.t;

}

for (int i = 0; i < 4; i++)

{

int tx = temp.x + dx[i], ty = temp.y + dy[i];

if (Ok (tx, ty))

{

qu.push (node (tx, ty, temp.t + 1));

vis[tx][ty] = true;

}

return -1;

}

int main()

{

// CFF;

int n;

while (scanf ("%d", &n) != EOF)

{

memset (vvis, false, sizeof (vvis));

for (int i = 1; i <= n; i++)

{

scanf ("%d%d%d", &aa[i].x, &aa[i].y, &aa[i].t);

vvis[aa[i].x][aa[i].y] = true;

for (int j = 0; j < 4; j++)

{

int tx = aa[i].x + dx[j], ty = aa[i].y + dy[j];

if (tx >= 0 && ty >= 0)

vvis[tx][ty] = true;

}

sort (aa + 1, aa + 1 + n);

printf ("%d\n", bfs (0, 0, 0));

}

return 0;

}

poj2431

maksyuki 发表于 oj 分类，标签: 基础算法-贪心, 数据结构-队列\双端\单调\优先

01 10月 2015

Expedition

A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to run over a rock and puncture the truck's fuel tank. The truck 阅读全文 »

poj3069

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

01 10月 2015

Saruman's Army

Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir 阅读全文 »

poj3617

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

01 10月 2015

Best Cow Line

FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year" competition. In this contest every farmer arranges his cows in a line and herds them past the judges.

The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows' names.

FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.

FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he's finished, FJ takes his cows for registration in this new order.

Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single initial ('A'..'Z') of the cow in the ith position in the original line

Output

The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows ('A'..'Z') in the new line.

Sample Input

Sample Output

ABCBCD

Source

USACO 2007 November Silver

题目类型：贪心

算法分析：如果头的字符比末尾的字符小，则输出头的字符，如果头的字符大于末尾的字符，则输出末尾的字符。如果相等，则需要找到第一个不相等的字符，然后输出这个字符是从头尾所走到的那个相同字符，注意最后输出的格式！！！

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 2e3 + 6;

char aa[maxn];

int main()
{
//   CFF;
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; i++)
            scanf (" %c", &aa[i]);

        int pa = 1, pb = n;
        int cnt = 0;
        while (pa <= pb)
        {
            bool is_left = false;
            for (int i = 0; pa + i <= pb; i++)
            {
                if (aa[pa+i] < aa[pb-i]) {is_left = true; break;}
                if (aa[pa+i] > aa[pb-i]) {is_left = false; break;}
            }

            if (cnt && cnt % 80 == 0)
                puts ("");

            if (is_left) printf ("%c", aa[pa++]);
            else printf ("%c", aa[pb--]);
            cnt++;
        }
        puts ("");
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 2e3 + 6;

char aa[maxn];

int main()

{

// CFF;

int n;

while (scanf ("%d", &n) != EOF)

{

for (int i = 1; i <= n; i++)

scanf (" %c", &aa[i]);

int pa = 1, pb = n;

int cnt = 0;

while (pa <= pb)

{

bool is_left = false;

for (int i = 0; pa + i <= pb; i++)

{

if (aa[pa+i] < aa[pb-i]) {is_left = true; break;}

if (aa[pa+i] > aa[pb-i]) {is_left = false; break;}

}

if (cnt && cnt % 80 == 0)

puts ("");

if (is_left) printf ("%c", aa[pa++]);

else printf ("%c", aa[pb--]);

cnt++;

}

puts ("");

}

return 0;

}

超客的水墨烟雨

poj3190

poj2376

Codeforces Round #323(Div.2) (2/5) (Div.1) (0/5)

BestCoder Round #58(Div.2) (4/4) (Div.1) (3/4)

A Card Game

poj3050

poj3669

poj2431

poj3069

poj3617

分类目录

标签云

书签

近期评论

2015年10月
一	二	三	四	五	六	日
« 9月				11月 »
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31