分类目录归档:贪心

B.上课上课上课 | 2018 校内选拔赛 预选赛 Day1

Description

ACSync 是个上课狂,大学期间曾立志要上完大学里所有的课,假设所有课都是年年开并且上课时间不变,聪明的你快来帮帮他算一下他的鸿鹄之志能否终成正果?

Input

第一行为 2 个数 N, M,分别表示课程的总数和 ACSync 可以上课的总年数;
接下来的 N 行,第 i 行为两个整数 Ai, Bi (Ai <= Bi),表示第 i 门课程的上课时间 [Ai, Bi]。

如果两门课的上课时间 [Ai, Bi] 和 [Aj, Bj] 有重合,则这两门课不能在同一年上。

对于全部测试用例,1 <= N <= 1 000; 1 <= M <= 1 000; 1 <= Ai <= Bi <= 1 000 000 000。

Output

ACSync 能否在 M 年内学完所有课程?若是,输出「Yes」,否则输出「No」。

Sample Input

3 2
1 2
2 3
3 4

Sample Output

Yes

Hint

测试样例(具体不唯一):

1 2 和 3 4 在第一年;
2 3 在第二年;
故可以。

使用结构体进行数据存储,构造 CMP 函数使用 Sort 对数组按结束时间进行排序。

题解

#include "cstring"
#include "cmath"
#include "algorithm"
#include "cstdio"
using namespace std;
struct node
{
    int start, end;//课程起止时间
    bool used;
};
inline bool cmp(node A, node B)
{
    if (A.start > B.start)//开始时间晚的课程放后边
        return 0;
    if (A.start == B.start && A.end > B.end)//开始时间相同,则结束时间晚的课程放后边
        return 0;
    return 1;
}
int main()
{
    int n,m;
    /**
     * n 课程数
     * m 年份数
     */
    scanf("%d%d", &n, &m);
    node course[n];
    memset(course, 0, sizeof(course));
    for (int i = 0; i < n; i++)
        scanf("%d%d", &course[i].start, &course[i].end);

    int sum = 0;
    for (int i = 0; i < m; i++)//i 当前年份
    {
        sort(course, course + n, cmp);
        int end = 0;//上节课的时间
        for (int j = 0; j < n; j++)
        {
            if (!course[j].used)
            {
                if (course[j].start > end)
                {
                    end = course[j].end;
                    course[j].used = 1;
                    sum++;
                }
            }
        }
    }
    //debug
    // printf("sum == %d\n", sum);
    printf(sum == n ? "Yes" : "No");
    return 0;
}

区间调度问题

Description

有 n 项工作,每项工作分别在 si 时间开始,在 ti 时间结束。对于每项工作,你都可以选择参与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(既是是开始的瞬间和结束的瞬间重叠也是不允许的)

你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?

Input

第一行输入一个数 n (1 ≤ n ≤ 100000),表示工作的数量
接下来的 n 行,第 1 + i (1 ≤ i ≤ n) 行包含两个数 si, ti (1 ≤ si ≤ ti ≤ 10^9),分别为起始时间和结束时间。

Output

输出为一行,包含一个整数,为能参与的工作数的最大值

Sample Input

5
1 3
2 5
4 7
6 9
8 10

Sample Output

3

Hint

每一次都选取结束时间最早的事件。因为与其他选择方案相比,该算法的选择方案在选取了相同数量的更早开始的工作时,
其最终结束时间不会比其他方案的更晚。所以,不存在选取更多工作的选择方案。
通过定义 compare 函数实现 sort() 的自定义排序规则。

题解

#include 
#include 
#include 
#include 
#include 
#include 
#define INF 100100
using namespace std;
int sum = 0;

struct node
{
    int start, end;
}arr[INF];

bool cmp(const node& i, const node& j)
{
    if (i.end > j.end)
        return 0;
    else
        if (i.end == j.end && i.start > j.start)
            return 0;
    return 1;
}

inline int find(int addr, int n)
{
    for (int i = addr + 1; i < n; i++)
        if (arr[i].start > arr[addr].end){
            return i;
        }
    return n+1;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &arr[i].start, &arr[i].end);
    sort(arr,arr+n,cmp);
    for (int addr = 0; addr < n; addr = find(addr, n))
        sum++;
    printf("%d\n", sum);
    return 0;
}

[POJ 3617]Best Cow Line

Description

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

6
A
C
D
B
C
B

Sample Output

ABCBCD

Hint

使用贪心算法,不断将较小的字符放入新字符串的末尾,这样我们就能构造一个字典序最小的串。对于首尾字符相同的情景,取哪个都可以。
注意题目要求,每 80 字符换行。

题解

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <cstring>
//#include <regex>
#define online
#define INF 2010
using namespace std;

int n, head, tail;
char str[INF];
string str2;
int chk_head,chk_tail;
inline bool check()
{
    #ifdef offline
    printf("new check\n");
    #endif
    chk_head = head;
    chk_tail = tail;
    while (chk_head <= chk_tail)
    {
        if (str[chk_head] == str[chk_tail])
        {
            #ifdef offline
            printf("str[chk_head] %d %c== str[chk_tail] %d %c\n", chk_head, str[chk_head], chk_tail, str[chk_tail]);
            #endif
            chk_head++;
            chk_tail--;
        }
        else
        {
            if (str[chk_head] > str[chk_tail])
            {
                str2 = str2 + str[tail];
                tail--;
                #ifdef offline
                printf("check end at tail\n");
                #endif
                return 1;//tail
            }
            else
            {
                str2 = str2 + str[head];
                head++;
                #ifdef offline
                printf("check end at head\n");
                #endif
                return 0;//head
            }
        }
    }
    str2 = str2 + str[tail];
    tail--;
    #ifdef offline
    printf("check end at outside\n");
    #endif
}
inline bool solve()
{
    #ifdef offline
    printf("new solve\n");
    #endif
    if (str[head] > str[tail]){
        str2 = str2 + str[tail];
        tail--;
        #ifdef offline
        printf("solve 1\n");
        #endif
    }
    else
    {
        #ifdef offline
        printf("solve 0\n");
        #endif

        if (str[head] == str[tail] && head != tail){
            #ifdef offline
            printf("head == tail ==  %d\n", head);
            #endif
            check();
        }
        else
        {
            str2 = str2 + str[head];
            head++;
        }
    }
    if (head > tail)
        return 0;
    else
        solve();
}

int main()
{
    //srand((unsigned int)(time(NULL)));
    //freopen("","r",stdin);
    //freopen("","W",stdout);
    scanf("%d", &n);
    head = 0;
    tail = n-1;
    for (int i = 0; i < n; i++)
        scanf("%c%c", &str[i], &str[i]);
    solve();
    //cout<<str2;//poisonous output format
    for (int i = 0; i < str2.length(); i++)
    {
        if ((i + 1) % 80 == 0){
            if (i + 1 == n)
                printf("%c", str2[i]);
            else
                printf("%c\n", str2[i]);
        }
        else
            printf("%c", str2[i]);
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

UOJ 2 【NOI2014】起床困难综合症

21 世纪,许多人得了一种奇怪的病:起床困难综合症,其临床表现为:起床难,起床后精神不佳。作为一名青春阳光好少年,atm 一直坚持与起床困难综合症作斗争。通过研究相关文献,他找到了该病的发病原因:在深邃的太平洋海底中,出现了一条名为 drd 的巨龙,它掌握着睡眠之精髓,能随意延长大家的睡眠时间。正是由于 drd 的活动,起床困难综合症愈演愈烈,以惊人的速度在世界上传播。为了彻底消灭这种病,atm 决定前往海底,消灭这条恶龙。

历经千辛万苦,atm 终于来到了 drd 所在的地方,准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能,他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来,drd 的防御战线由 n 扇防御门组成。每扇防御门包括一个运算 op 和一个参数 t,其中运算一定是 OR,XOR,AND 中的一种,参数则一定为非负整数。如果还未通过防御门时攻击力为 x,则其通过这扇防御门后攻击力将变为 x op t。最终drd 受到的伤害为对方初始攻击力 x 依次经过所有 n 扇防御门后转变得到的攻击力。

由于 atm 水平有限,他的初始攻击力只能为 0 到 m 之间的一个整数(即他的初始攻击力只能在 0,1,…,m 中任选,但在通过防御门之后的攻击力不受 m 的限制)。为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害,请你帮他计算一下,他的一次攻击最多能使 drd 受到多少伤害。

输入格式

第一行包含两个整数,依次为 n,m,表示 drd 有 n 扇防御门,atm 的初始攻击力为 0 到 m 之间的整数。

接下来 n 行,依次表示每一扇防御门。每行包括一个字符串 op 和一个非负整数 t,两者由一个空格隔开,且 op 在前,t 在后,op 表示该防御门所对应的操作,t 表示对应的参数。

输出格式

一行一个整数,表示 atm 的一次攻击最多使 drd 受到多少伤害。

样例一

input

3 10
AND 5
OR 6
XOR 7

output

1

explanation

atm可以选择的初始攻击力为 0,1,…,10。

假设初始攻击力为4,最终攻击力经过了如下计算
4 AND 5 = 4
4 OR 6 = 6
6 XOR 7 = 1

类似的,我们可以计算出初始攻击力为 1,3,5,7,9 时最终攻击力为 0,初始攻击力为 0,2,4,6,8,10 时最终攻击力为 1,因此 atm 的一次攻击最多使 drd 受到的伤害值为 1。

题解

30pt Brute

#include "cmath"
#include "cstring"
#include "cstdlib"
#include "cstdio"
#include "iostream"
#include "algorithm"
#define rep(i,l,r) for(i = l;i < r; i++)
#define derep(i,l,r) for(i = l;i > r; i--)
#define maxn 110000
#define N 1074000000
using namespace std;
long long i,j,k;
long long n,m,a;
long long ATK,atk = 0;
char c;

/*
 * m	DEF limit
 * a	ATK
 * c	Command class just the "op" in the question
 * h	hurt
 */

struct node
{
	char c[4];
	long long a;
}P[maxn];

inline void Solve(long long i)
{
	atk = i;
	rep(j,0,n)
	{
		if (P[j].c[0] == 'A')
		{
			//printf("%lld & %lld = ",atk,P[j].a);
			atk = atk & P[j].a;
		}
		if (P[j].c[0] == 'O')
		{
			//printf("%lld | %lld = ",atk,P[j].a);
			atk = atk | P[j].a;
		}
		if (P[j].c[0] == 'X')
		{
			//printf("%lld xor %lld = ",atk,P[j].a);
			atk = atk ^ P[j].a;
		}
		//printf("%lld\n", atk);
	}
	//printf("atk=%d\n",atk);
	if (atk > ATK)
		ATK = atk;
	//printf("ATK=%d\n", ATK);
}

void Init()
{
	scanf("%lld%lld",&n,&m);
	rep(i,0,n)
		scanf("%s%lld", P[i].c, &P[i].a);

	rep(i,0,m+1)
	Solve(i);

	printf("%lld\n", ATK);
}


int main()
{
	freopen("2.in","r",stdin);
	
	Init();

	fclose(stdin);
	return 0;
}