Greedy

http://acm.hdu.edu.cn/showproblem.php?pid=6034 题意： # 有一个仅由小写字母组成的字符串，要求将a..z的字母，对应到0..25，每个数字只能被一个字母对应，得到一个26进制的数，现在问这个数最大是多少。注意不允许有前导0，除非这个数本身就是0.

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

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

有 n 个字符串，每个字符串都是由 A-J 的大写字符构成。现在你将每个字符映射为一个 0-9 的数字，不同字符映射为不同的数字。这样每个字符串就可以看做一个整数，唯一的要求是这些整数必须是正整数且它们的字符串不能有前导零。现在问你怎样映射字符才能使得这些字符串表示的整数之和最大？ 输入描述：每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n ， 接下来有 n 行，每行一个长度不超过 12 且仅包含大写字母 A-J 的字符串。 n 不大于 50，且至少存在一个字符不是任何字符串的首字母。 输出描述：输出一个数，表示最大和是多少。 输入例子： 2 ABC BCA 输出例子： 1875 一开始看漏了首位不能映射到0的条件…直接贪了..结果发现不太对…

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

题目链接 题意：给出n,m，n个数，对其中的一些数进行修改，要求1..m中出现次数最少的数最大，输出这个最少的数最大是多少，以及修改的次数。 思路：最小的数最多出现n/m次。

题目链接 傻逼模拟。。读完题就ac了。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月07日 星期日 18时04分18秒 4File Name :code/whust2016/#1/D.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=280; 34int n,m; 35int total,adva,advb; 36struct Friend 37{ 38 int money; 39 int adv; 40}f[N]; 41struct Room 42{ 43 int type; 44 int cost; 45 int adv; 46}r[N]; 47struct Ans 48{ 49 int val; 50 int rid; 51 int fid; 52 bool operator < (Ans b)const 53 { 54 return val>b.val; 55 } 56}ans[300*300]; 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 cin>>total>>adva>>advb; 63 cin>>n; 64 for ( int i = 1 ; i <= n ; i++) 65 scanf("%d %d",&f[i].money,&f[i].adv); 66 scanf("%d",&m); 67 for ( int i = 1 ; i <= m ; i++) 68 scanf("%d%d%d",&r[i].type,&r[i].cost,&r[i].adv); 69 int cnt = 0 ; 70 for ( int i = 1 ; i <= m ; i++) 71 { 72 if (r[i].type==1) 73 { 74 if (r[i].cost<=total) 75 { 76 cnt++; 77 ans[cnt].val = r[i].adv+adva; 78 ans[cnt].rid = i; 79 ans[cnt].fid = -1; 80 } 81 continue; 82 } 83 else 84 { 85 for ( int j = 0 ; j <= n ; j++) 86 { 87 if (j==0) //自己住双人间 88 { 89 if (r[i].cost<=total) 90 { 91 cnt++; 92 ans[cnt].val = r[i].adv+advb; 93 ans[cnt].rid = i ; 94 ans[cnt].fid = -1; 95 } 96 } 97 else 98 { 99 if (r[i].cost<=total*2&&r[i].cost<=f[j].money*2) 100 { 101 cnt++; 102 ans[cnt].val = r[i].adv+f[j].adv; 103 ans[cnt].rid = i ; 104 ans[cnt].fid = j; 105 } 106 } 107 } 108 } 109 } 110// for ( int i = 1 ; i <= cnt ; i++) 111// { 112// printf("val:%d room: %d friend : %d \n",ans[i].val,ans[i].rid,ans[i].fid); 113// } 114 if (cnt==0) 115 { 116 puts("Forget about apartments. Live in the dormitory."); 117 }else 118 { 119 sort(ans+1,ans+cnt+1); 120 if (r[ans[1].rid].type==1) 121 { 122 printf("You should rent the apartment #%d alone.\n",ans[1].rid); 123 } 124 else 125 { 126 if (ans[1].fid==-1) 127 { 128 printf("You should rent the apartment #%d alone.\n",ans[1].rid); 129 } 130 else 131 { 132 133 printf("You should rent the apartment #%d with the friend #%d.\n",ans[1].rid,ans[1].fid); 134 135 } 136 } 137 } 138 #ifndef ONLINE_JUDGE 139 fclose(stdin); 140 #endif 141 return 0; 142}

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为了取得冠军，他就必须使新队列的字典序尽量小。给你初始奶牛序列(用头字母)表示，然后按照上述的规则组成新序列，并使新序列的字典序尽量小。

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.

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. //有三个头牛，下面三行二个数分别代表其体重及力量 //它们玩叠罗汉的游戏，每个牛的危险值等于它上面的牛的体重总和减去它的力量值，因为它要扛起上面所有的牛嘛. //求所有方案中危险值最大的最小

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)．

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个时间的开始和截止时间，保证没有两个时间的开始或者截止时间相同，问有多少个时间被包含在其他事件中。即aj < ai and bi < bj. 思路：没有两个事件的时间相同很关键。 那么我们可以直接按照开始时间为关键字排序，然后结束时间取之前发生了的（可能还没发生完）时间的结束时间的最大值即可。

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

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

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

http://140.114.86.238/problem/10925/ Description 有兩個序列S1和S2，各有N個元素。當我們在S1,S2各取一個數字時，總共會有NN這麼多可能的”和”(sum)。請找出這NN這麼多和裡最小的N個值，並將它們加總後輸出。

http://codeforces.com/contest/613/problem/B 题意：有n个技能，初始每个技能的level为a[i]，每个技能最大level为A(不妨称为满级技能)，设满级技能个数为maxnum，最小的技能level为minval，问如何将m个技能点分配到n个技能上使得cfmaxsum+cmminval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3693 题意： n+2个人取吃饭，每人w元，每k个人可以少付一个人的钱，问最后两个教练每人要付多少钱。 思路：贪心。坑点在读题。。选手n个人，不要忘记两个教练，以及，钱数是两个教练平分。

http://codeforces.com/contest/373/problem/C 题意：n个袋鼠，每个袋鼠的size为a[i]，一只袋鼠的size至少是另一只两倍时才能将它装下，被装下的袋鼠不能再装别的袋鼠且不能被看见。问能看见的袋鼠最少是多少。 思路：贪心。最多有n/2个袋鼠被装下。先排序，然后贪心即可。