NOI题库刷题日志 (贪心篇题解)

这段时间在NOI题库上刷了刷题,来写点心得和题解

一、寻找平面上的极大点

2704:寻找平面上的极大点

总时间限制: 
1000ms 
内存限制: 
65536kB
描述
在一个平面上,如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b),这是指x>=a,y>=b;

用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。

给定n个点的集合,一定存在若干个点,它们不会被集合中的任何一点所支配,这些点叫做极大值点。

编程找出所有的极大点,按照x坐标由小到大,输出极大点的坐标。

本题规定:n不超过100,并且不考虑点的坐标为负数的情况。
输入
输入包括两行,第一行是正整数n,表示是点数,第二行包含n个点的坐标,坐标值都是整数,坐标范围从0到100,输入数据中不存在坐标相同的点。
输出
x轴坐标最小到大的顺序输出所有极大点。

输出格式为:(x1,y1),(x2,y2),...(xk,yk)

注意:输出的每个点之间有","分隔,最后一个点之后没有",",少输出和多输出都会被判错
样例输入
5
1 2 2 2 3 1 2 3 1 4
样例输出
(1,4),(2,3),(3,1)
提示
NOI题库刷题日志 (贪心篇题解)
这个题一看水水的贪心( ⊙ o ⊙ )!于是开心的去刷代码去了。。。
大体思路就是:先读入所有的坐标,然后从大到小排序(此处不排序会使后面的处理无法最优),然后顺序扫描一遍所有的点,然后与当前的极大点进行比较,如果被覆盖就continue,否则加入存极大点的数组,由于之前从大到小排序,所以不会出现什么问题,最后倒序输出就好了O(∩_∩)O~~
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct data{
int x,y;
};
int cmp(data x,data y)
{
if (x.x>y.x)
return 0;
else
if (x.x==y.x)
{
if (x.y>y.y)
return 0;
else
return 1;
}
else
return 1;
}
int cmp1(data x,data y)
{
if (x.x>y.x)
return 1;
else
if (x.x==y.x)
{
if (x.y>y.y)
return 1;
else
return 0;
}
else
return 0;
}
int main()
{
int n;int i,j;
bool f=false;
data d[1000]={0};
data dandan[1000]={0};
int a,b;
int k=0;
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d%d",&dandan[i].x,&dandan[i].y);
sort(dandan+1,dandan+n+1,cmp1);
// for (i=1;i<=n-1;i++)
// cout<<"("<<dandan[i].x<<","<<dandan[i].y<<")"<<",";
// cout<<"("<<dandan[n].x<<","<<dandan[n].y<<")"<<endl;
for (i=1;i<=n;i++)
{
a=dandan[i].x;b=dandan[i].y;
f=false;
for (j=1;j<=k;j++)
if (d[j].x>=a && d[j].y>=b)
{
f=true;
break;
}
if (f)
continue;
else
{
k++;
d[k].x=a;
d[k].y=b;
}
}
sort(d+1,d+k+1,cmp);
for (i=1;i<=k-1;i++)
cout<<"("<<d[i].x<<","<<d[i].y<<")"<<",";
cout<<"("<<d[k].x<<","<<d[k].y<<")";
return 0;
}

由于当时编程时光顾着看旁边的蛋神颓Agar了,分心代码写的有点残。。。


二、电池的寿命
      这个题比刚刚就恶心了点,但是代码也短了,果然是短小啊;-)

2469:电池的寿命

总时间限制: 
1000ms 
内存限制: 
65536kB
描述

小S新买了一个掌上游戏机,这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏,他买了很多5号电池,这些电池的生产商不同,质量也有差异,因而使用寿命也有所不同,有的能使用5个小时,有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时,那么他只能玩3个小时的游戏,有一个电池剩下的电量无法使用,但是如果他有更多的电池,就可以更加充分地利用它们,比如他有三个电池分别能用3、3、5小时,他可以先使用两节能用3个小时的电池,使用半个小时后再把其中一个换成能使用5个小时的电池,两个半小时后再把剩下的一节电池换成刚才换下的电池(那个电池还能用2.5个小时),这样总共就可以使用5.5个小时,没有一点浪费。

现在已知电池的数量和电池能够使用的时间,请你找一种方案使得使用时间尽可能的长。

输入

输入包含多组数据。每组数据包括两行,第一行是一个整数N (2 ≤ N ≤ 1000),表示电池的数目,接下来一行是N个正整数表示电池能使用的时间。

输出

对每组数据输出一行,表示电池能使用的时间,保留到小数点后1位。

样例输入
2
3 5
3
3 3 5
样例输出
3.0
5.5

      大体思路:先计算所有的电池的总量,然后进行比较,如果总量减去最大的那个,比最大的小,就可以用所有小的和最大的打车轮战,来耗最大的电量,这时最大的用电量就是  总和减去最大的值;如果比最大的大,那么用电量就是总量的一半,此处是可以证明的,但就不多提了
  下面看代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int dc[1100]={0};
int main()
{
int n;
while (scanf("%d",&n)==1)
{
int i;
int sum=0;
double ans=0.0;
//cin>>n;
memset(dc,0,sizeof(dc));
for (i=1;i<=n;i++)
{
scanf("%d",&dc[i]);
sum+=dc[i];
}
sort(dc+1,dc+n+1);
if (sum-dc[n]>dc[n])
ans=sum*1.0/2.0;
else
ans=sum*1.0-dc[n]*1.0;
printf("%0.1f\n",ans);
}
return 0;
}

三、最大子矩阵和

1768:最大子矩阵

总时间限制: 
1000ms 
内存限制: 
65536kB
描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。



比如,如下4 * 4的矩阵



0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2



的最大子矩阵是



9 2

-4 1

-1 8



这个子矩阵的大小是15。
输入
输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数,整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[-127, 127]。
输出
输出最大子矩阵的大小。
样例输入
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1 8 0 -2
样例输出
15

     然而,看到这个题出现在贪心中,其实,其实我是拒绝的,所以我还是用了个DP,因为不会用贪心做他。。。
    然而这个题其实和最大子矩阵和有异曲同工之妙,就是稍稍复杂了些
闲话少说,代码:
#include<iostream>
#include<cstring>
using namespace std;
int a[101][101],b[101];
int dp(int a[],int n)
{ int sum=0,max=0;
for (int i=1; i<=n; i++)
{
sum+=a[i];
if (sum<0)sum=0;
if (sum>max)max=sum;
}
return max;
}
int main()
{
int i,j,n;
cin>>n;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
cin>>a[i][j];
int sum=0,max=0;
for (i=1; i<=n; i++)
for (j=i; j<=n; j++)
{
memset(b,0,sizeof(b));
for (int l=1; l<=n; l++)
for (int k=i; k<=j; k++)
b[l]+=a[k][l];
sum=dp(b,n);
if (max<sum)max=sum;
}
cout<<max<<endl;
return 0;
}

以后还会刷的,顺便提一句,我发现高中时间好紧( ⊙ o ⊙ )啊!不努力不行啊,╮(╯▽╰)╭


上一篇:Linux查看硬件信息命令


下一篇:noi题库(noi.openjudge.cn) 1.8编程基础之多维数组T11——T20