这次总结了一下第二周贪心几道有意思一点的题目
HDU - 1789：
交大校队刚从2018焦作站ACM/ICPC回来。现在他有很多作业要做。每个老师给他一个交作业的最后期限。
如果他们在最后期限后交作业，老师就会降低他的期末成绩。
现在我们假设每个人做作业都需要一天。
所以他们想到了要安排做作业的顺序，把降低的分数降到最低。
请帮助他们。
Input
输入包含T个测试用例。输入的第一行是单个整数T，为测试用例的数量。
每个测试用例以一个正整数N开头(1<=N<=1000)，表示作业的数量。
然后两行。第一行包含N个整数，表示受试者的截止日期，下一行包含N个整数，表示降低的分数。
Output
对于每个测试用例，您应该输出最小的总降低分数，每个测试用例一行。
Sample Input
3
3
3 3 3
10 5 1
3
1 3 1
6 2 3
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4
Sample Output
0
3
5
Hint
上方有三组样例。
对于第一组样例，有三个作业它们的截止日期均为第三天，每天做一个正好在截止日期前全部做完，所以没有扣分，输出0。
对于第二组样例，有三个作业，它们的截止日期分别为第一天，第三天、第一天。第一天做了第一个作业，第二天做了第二个作业，共扣了3分，输出3。
这道题的思想其实很简单，就是要将分值高的题目科目作业先做，然后往后以此类推
AC代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
typedef struct node{
int day;
int loss;
}score;
//降序排序
bool cmp(score a,score b){
return a.loss > b.loss;
}
int main()
{
int N,n,ans;
score mark[1010];
scanf("%d",&N);
while(N--){
ans = 0;
scanf("%d",&n);
//输入数值
for(int i = 0;i < n;i++)
scanf("%d",&mark[i].day);
for(int i = 0;i < n;i++)
scanf("%d",&mark[i].loss);
//分值由大到小排序
std::sort(mark,mark+n,cmp);
int plan[1000];
//初始化
memset(plan,0,sizeof(plan));
for(int i = 0;i < n;i++){
if(plan[mark[i].day] == 0){
plan[mark[i].day]++;
continue;
}
int j = mark[i].day;
while(j--){
if(plan[j] == 1){
continue;
}
else{
plan[j]++;
break;
}
}
if(j < 1){
ans += mark[i].loss;
}
}
printf("%d\n",ans);
}
return 0;
}
HDU - 2037
“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%…”
确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）
Input
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。
Output
对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。
Sample Input
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
Sample Output
5
我们要保证看到的节目数量最多，那么就将节目按照结束时间早晚的顺序进行排序，然后用区间不相交（节目播出时间不重复）作为判定是否对看到节目数加一的依据就行了
下面是AC代码
#include <stdio.h>
#include<algorithm>
typedef struct node{
int t_start;
int t_end;
}node;
bool cmp(node a,node b){
return a.t_end < b.t_end;
}
int main()
{
while(1){
int n;
scanf("%d",&n);
if(n == 0)
break;
node times[110];
for(int i = 0;i < n;i++)
scanf("%d %d",×[i].t_start,×[i].t_end);
std::sort(times,times+n,cmp);
int count = 0;
int end = 0;
for(int i = 0;i < n;i++){
if(times[i].t_start >= end){
end = times[i].t_end;
count++;
}
}
printf("%d\n",count);
}
return 0;
}
CodeForces - 934B
Apart from Nian, there is a daemon named Sui, which terrifies children and causes them to become sick. Parents give their children money wrapped in red packets and put them under the pillow, so that when Sui tries to approach them, it will be driven away by the fairies inside.
Big Banban is hesitating over the amount of money to give out. He considers loops to be lucky since it symbolizes unity and harmony.
He would like to find a positive integer n not greater than 1018, such that there are exactly k loops in the decimal representation of n, or determine that such n does not exist.
A loop is a planar area enclosed by lines in the digits’ decimal representation written in Arabic numerals. For example, there is one loop in digit 4, two loops in 8 and no loops in 5. Refer to the figure below for all exact forms.
Input
The first and only line contains an integer k (1 ≤ k ≤ 106) — the desired number of loops.
Output
Output an integer — if no such n exists, output -1; otherwise output any such n. In the latter case, your output should be a positive decimal integer not exceeding 1018.
Examples
Input
2
Output
462
Input
6
Output
8080
这道题其实比较坑，我们很容易会被题目的样例输出误导，
其实，它题目已经说了，输出多种解其中的一种就可以了，
不过它有限制条件，输出数据大小要小于 十的十八次方 ，
所以我们一个是考虑数位上的数字要尽量大，
另外，只需要考虑输出有一个圈的9和两个圈的8就可以了
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int num_2,num_1;
num_1 = n%2;
num_2 = n/2;
if(n == 0){
printf("1");
printf("\n");
return 0;
}
if(n<=36){
for(int i = 0;i < num_2;i++){
printf("8");
}
for(int i = 0;i < num_1;i++){
printf("9");
}
}
else{
printf("-1");
}
printf("\n");
return 0;
}