codeforces #413 B T-shirt buying (贪心)

题目链接

题意:有n个T恤,每个价格都不同,有三种颜色,分别用1,2,3表示,每件T恤给出前xiong和后背的颜色。现在有m个顾客排成一队,对于每个顾客,给出他喜欢的颜色,只要一个T恤的前xiong或者后背的颜色之一满足该颜色即可。顾客总希望买符合他喜欢颜色的T恤中价格最低的。现在问每个顾客买到的T恤的价格,如果某个顾客没有买T恤,输出-1

思路:贪一下?

对于每个颜色,找到价格最低的。记录的时候顺便记录id,以标记某件有2个颜色的衣服是否卖出去了。

1A美滋滋

 

今日头条2017秋招笔试_1

头条校招(今日头条2017秋招真题)

头条的2017校招开始了!为了这次校招,我们组织了一个规模宏大的出题团队。每个出题人都出了一些有趣的题目,而我们现在想把这些题目组合成若干场考试出来。在选题之前,我们对题目进行了盲审,并定出了每道题的难度系数。一场考试包含3道开放性题目,假设他们的难度从小到大分别为a, b, c,我们希望这3道题能满足下列条件:

a<= b<= c
b – a<= 10
c – b<= 10

所有出题人一共出了n道开放性题目。现在我们想把这n道题分布到若干场考试中(1场或多场,每道题都必须使用且只能用一次),然而由于上述条件的限制,可能有一些考试没法凑够3道题,因此出题人就需要多出一些适当难度的题目来让每场考试都达到要求。然而我们出题已经出得很累了,你能计算出我们最少还需要再出几道题吗?

输入输入的第一行包含一个整数n,表示目前已经出好的题目数量。

第二行给出每道题目的难度系数 d1, d2, …, dn。

样例输入4

20 35 23 40

输出输出只包括一行,即所求的答案。

样例输出2

时间限制C/C++语言:1000MS其它语言:3000MS
内存限制C/C++语言:65536KB其它语言:589824K

 

div2 A的难度…直接贪就好,不给数据范围的都是耍流氓…

 

 

今日头条笔试题-最大映射(贪心)

一开始看漏了首位不能映射到0的条件…直接贪了..结果发现不太对…

哦贪心的方法就是算每个字母的权值和…用pair 搞一下…

处理的办法是如果10个字母都出现,那么先把没有在首位出现过的字母中权重最小的那个映射到0,再搞剩下的…

一个trick是…map映射到0..和某个key没有被映射过..产生了二义性….

窝的做法就是整体+1,最后再减回来..

然后因为某处手残卡了1个小时…???.

哎我果然是个废k了…..傻逼贪心都写不对QAQ

 

codeforces #375 D. Lakes in Berland (dfs)

题目链接

题意:n*m个格子,有*和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合,且任何一个.不在边界上。现在给出一个n*m的图保证至少有k个湖。问填多少个.成*,才能使得恰好有k个湖。

思路:贪心,先处理出所有的湖的大小,然后从小往大填。

注意dfs的时候如果某个“可能”的湖遇到了边界,要把之前打的标记撤销掉。

 

 

codeforces #375 C. Polycarp at the Radio (贪心)

题目链接

题意:给出n,m,n个数,对其中的一些数进行修改,要求1..m中出现次数最少的数最大,输出这个最少的数最大是多少,以及修改的次数。

思路:最小的数最多出现n/m次。

竟然因为排序后下标变乱不知所措40分钟。。。我也是醉了。。。

 

 

whust 2016 #1 D Zhenya moves from the dormitory (贪心,模拟)

题目链接
傻逼模拟。。读完题就ac了。。。

BZOJ 1640/1692 : [Usaco2007 Nov]Best Cow Line 队列变换 (贪心)

 

1640: [Usaco2007 Nov]Best Cow Line 队列变换

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 710  Solved: 373
[Submit][Status][Discuss]

Description

FJ打算带着他可爱的N (1 ≤ N ≤ 2,000)头奶牛去参加”年度最佳老农”的比赛.在比赛中,每个农夫把他的奶牛排成一列,然后准备经过评委检验. 比赛中简单地将奶牛的名字缩写为其头字母(the initial letter of every cow),举个例子,FJ带了Bessie, Sylvia,和Dora,那么就可以缩写为BSD. FJ只需将奶牛的一个序列重新排列,然后参加比赛.他可以让序列中的第一头奶牛,或者最后一头走出来,站到新队列的队尾. 利欲熏心的FJ为了取得冠军,他就必须使新队列的字典序尽量小. 给你初始奶牛序列(用头字母)表示,然后按照上述的规则组成新序列,并使新序列的字典序尽量小.

Input

第1行:一个整数N.

第2行至第N+1行:每行一个大写字母,表示初始序列中该奶牛的头字母.

Output

得到的最小字典序的序列.每输出80个字母需要一个换行!

Sample Input

6
A
C
D
B
C
B

Sample Output

ABCBCD

HINT

Source

 

思路:比较麻烦的一个贪心。。对拍才找出了一个错误。。。

写丑了QAQ

 

BZOJ 1634: [Usaco2007 Jan]Protecting the Flowers 护花(贪心)

1634: [Usaco2007 Jan]Protecting the Flowers 护花

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 605  Solved: 383
[Submit][Status][Discuss]

Description

Farmer John went to cut some wood and left N (2 <= N <= 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cows were in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport the cows back to their barn. Each cow i is at a location that is Ti minutes (1 <= Ti <= 2,000,000) away from the barn. Furthermore, while waiting for transport, she destroys Di (1 <= Di <= 100) flowers per minute. No matter how hard he tries,FJ can only transport one cow at a time back to the barn. Moving cow i to the barn requires 2*Ti minutes (Ti to get there and Ti to return). Write a program to determine the order in which FJ should pick up the cows so that the total number of flowers destroyed is minimized.

约翰留下他的N只奶牛上山采木.他离开的时候,她们像往常一样悠闲地在草场里吃草.可是,当他回来的时候,他看到了一幕惨剧:牛们正躲在他的花园里,啃食着他心爱的美丽花朵!为了使接下来花朵的损失最小,约翰赶紧采取行动,把牛们送回牛棚. 牛们从1到N编号.第i只牛所在的位置距离牛棚Ti(1≤Ti《2000000)分钟的路程,而在约翰开始送她回牛棚之前,她每分钟会啃食Di(1≤Di≤100)朵鲜花.无论多么努力,约翰一次只能送一只牛回棚.而运送第第i只牛事实上需要2Ti分钟,因为来回都需要时间.    写一个程序来决定约翰运送奶牛的顺序,使最终被吞食的花朵数量最小.

Input

* Line 1: A single integer

N * Lines 2..N+1: Each line contains two space-separated integers, Ti and Di, that describe a single cow’s characteristics

第1行输入N,之后N行每行输入两个整数Ti和Di.

Output

* Line 1: A single integer that is the minimum number of destroyed flowers

一个整数,表示最小数量的花朵被吞食.

Sample Input

6
3 1
2 5
2 3
3 2
4 1
1 6

Sample Output

86

HINT

约翰用6,2,3,4,1,5的顺序来运送他的奶牛.

 

思路:和bzoj1629一样的思路。 对于两只牛,他们的先后顺序对于其他牛没有影响。

所以可以按照t*2+d升序排列。

 

BZOJ 1629: [Usaco2007 Demo]Cow Acrobats (贪心)

1629: [Usaco2007 Demo]Cow Acrobats

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 771  Solved: 398
[Submit][Status][Discuss]

Description

Farmer John’s N (1 <= N <= 50,000) cows (numbered 1..N) are planning to run away and join the circus. Their hoofed feet prevent them from tightrope walking and swinging from the trapeze (and their last attempt at firing a cow out of a cannon met with a dismal failure). Thus, they have decided to practice performing acrobatic stunts. The cows aren’t terribly creative and have only come up with one acrobatic stunt: standing on top of each other to form a vertical stack of some height. The cows are trying to figure out the order in which they should arrange themselves within this stack. Each of the N cows has an associated weight (1 <= W_i <= 10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a cow collapsing is equal to the combined weight of all cows on top of her (not including her own weight, of course) minus her strength (so that a stronger cow has a lower risk). Your task is to determine an ordering of the cows that minimizes the greatest risk of collapse for any of the cows. //有三个头牛,下面三行二个数分别代表其体重及力量 //它们玩叠罗汉的游戏,每个牛的危险值等于它上面的牛的体重总和减去它的力量值,因为它要扛起上面所有的牛嘛. //求所有方案中危险值最大的最小

Input

* Line 1: A single line with the integer N. * Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.

Output

* Line 1: A single integer, giving the largest risk of all the cows in any optimal ordering that minimizes the risk.

Sample Input

3
10 3
2 5
3 3

Sample Output

2

OUTPUT DETAILS:

Put the cow with weight 10 on the bottom. She will carry the other
two cows, so the risk of her collapsing is 2+3-3=2. The other cows
have lower risk of collapsing.

思路:贪心。 两头奶牛的相对位置,对于其他奶牛是没有影响的。因为这两头奶牛的体重之和一定。
那么对于两头奶牛i,j,谁放在下面呢?
如果i放在下面  代价为 s[i]-w[j],如果j放在下面 ,代价为s[j]-w[i];
当且仅当 s[i]-w[j]<s[j]-w[i],也就是 s[i]+w[i]<s[j]+w[j]时,i放在下面。
所以以s[i]+w[i]的和为关键字排序就好。

BZOJ 1623: [Usaco2008 Open]Cow Cars 奶牛飞车 (贪心)

1623: [Usaco2008 Open]Cow Cars 奶牛飞车

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 386  Solved: 266
[Submit][Status][Discuss]

Description

  编号为1到N的N只奶牛正各自驾着车打算在牛德比亚的高速公路上飞驰.高速公路有M(1≤M≤N)条车道.奶牛i有一个自己的车速上限Si(l≤Si≤1,000,000).
    在经历过糟糕的驾驶事故之后,奶牛们变得十分小心,避免碰撞的发生.每条车道上,如果某一只奶牛i的前面有K只奶牛驾车行驶,那奶牛i的速度上限就会下降K*D个单位,也就是说,她的速度不会超过Si – kD(O≤D≤5000),当然如果这个数是负的,那她的速度将是0.牛德比亚的高速会路法规定,在高速公路上行驶的车辆时速不得低于/(1≤L≤1,000,000).那么,请你计算有多少奶牛可以在高速公路上行驶呢?

Input

第1行输入N,M,D,L四个整数,之后N行每行一个整数输入Si.
N<=50000

Output

    输出最多有多少奶牛可以在高速公路上行驶.

Sample Input

3 1 1 5//三头牛开车过一个通道.当一个牛进入通道时,它的速度V会变成V-D*X(X代表在它前面有多少牛),它减速后,速度不能小于L
5
7
5

INPUT DETAILS:

There are three cows with one lane to drive on, a speed decrease
of 1, and a minimum speed limit of 5.

Sample Output

2

OUTPUT DETAILS:

Two cows are possible, by putting either cow with speed 5 first and the cow
with speed 7 second.

思路:贪心。尽可能让这些车均匀分布。 以及初始就干掉那些最大速度小于L的。然后按照s[i]从小到大排序,先放置速度小的。

BZOJ 1620: [Usaco2008 Nov]Time Management 时间管理 (贪心)

1620: [Usaco2008 Nov]Time Management 时间管理

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 636  Solved: 387
[Submit][Status][Discuss]

Description

Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1..N (1 <= N <= 1,000) to accomplish (like milking the cows, cleaning the barn, mending the fences, and so on). To manage his time effectively, he has created a list of the jobs that must be finished. Job i requires a certain amount of time T_i (1 <= T_i <= 1,000) to complete and furthermore must be finished by time S_i (1 <= S_i <= 1,000,000). Farmer John starts his day at time t=0 and can only work on one job at a time until it is finished. Even a maturing businessman likes to sleep late; help Farmer John determine the latest he can start working and still finish all the jobs on time.

N个工作,每个工作其所需时间,及完成的Deadline,问要完成所有工作,最迟要什么时候开始.

Input

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: T_i and S_i

Output

* Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.

Sample Input

4
3 5
8 14
5 20
1 16

INPUT DETAILS:

Farmer John has 4 jobs to do, which take 3, 8, 5, and 1 units of
time, respectively, and must be completed by time 5, 14, 20, and
16, respectively.

Sample Output

2

OUTPUT DETAILS:

Farmer John must start the first job at time 2. Then he can do
the second, fourth, and third jobs in that order to finish on time.

思路:贪心。一眼题。5分钟A掉,爽。 按照s[i]排序,然后完成前i个任务的最晚开始时间为 s[i]-sum ,sum为t[1]+…+t[i]..
如果ans<0,说明无法完成,赋值为-1.

codeforces 137 C. History (sorting,贪心)

题目链接
题意:给出n个时间的开始和截止时间,保证没有两个时间的开始或者截止时间相同,问有多少个时间被包含在其他事件中。即aj < ai and bi < bj. 思路:没有两个事件的时间相同很关键。 那么我们可以直接按照开始时间为关键字排序,然后结束时间取之前发生了的(可能还没发生完)时间的结束时间的最大值即可。

hdu 5646 ||bc #76 div 2 (贪心)

题目链接

题意:将正整数n(n<=1E9),拆分成k个(k<=1E9)个互不相等的正整数,并且使得k个正整数的乘积最大。如果可以拆分,输出最大乘积,否则输出-1.

思路:其实是道贪心。。容易知道,k个互不相同的正整数的最小的和为sum=(k+1)*k/2,以此来判断是否有解。如果有解。那么找到最大的i,使得从i 开始的连续k个正整数相加的和小于等于n.

由于k不会超过1E5(否则一定无解),所以可以开个数组存一下拆分的每个数。

然后设此时还需要添加r才能到n,那么贪心得想,一定是给最大的r个每个增加1最后的乘积会最大。这等效于直接将第k-r+1个直接增加r.

注意全程long long

以及:

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

原因是puts也是<stdio.h>里的。。

c和c++各有一套指针。。随时同步,所以cin会慢。。关掉同步会快,但是由于已经关掉同步了,混用就会有问题。 以前不知道puts也是不能混用的QAQ

 

 

 

codeforces croc 2016 B. Mischievous Mess Makers (贪心)

题目链接
题意:长度为n的初始为1,2,3…n的序列,最多进行k次两个数交换,变换后的序列中最懂能有多少逆序对。
思路:贪心得想。。每次变最外层的对答案贡献最多。 以及,最能能变化n/2次。

codeforces #345 div2 A. Joysticks (贪心)

题目链接
题意:两个手柄? 初始的电量给出,只有一个充电器,每经过一秒,充着电的手柄电量增加1,没有充电的手柄电量减少2,允许电量充到%100以上,当有电量为0的时候,或者当某一分钟开始的时候有手柄电量为1,游戏立即结束。问最多能玩多少时间游戏。

 

思路:贪心。。每次给电量少的充电。 坑点在于当某一时刻有手柄电量为1,那么游戏在进行这一分钟之前就结束。