博主欢迎转载，但请给出本文链接，我尊重你，你尊重我，谢谢~
http://www.cnblogs.com/chenxiwenruo/p/8660814.html
特别不喜欢那些随便转载别人的原创文章又不给出链接的
所以不准偷偷复制博主的博客噢~~
1. 自定义排序
第一题是第一行给出n(1<=n<=100)，表示下面有n行，每行A(0<=A<24)和B(0<=B<60)，表示定的闹钟为AhBmin。
接下来给定X，表示小明从起床到教室需要X分钟，最后一行给出A(0<=A<24)和B(0<=B<60)表示上课时间AhBmin。
求问小明赶在上课前，能够定的最晚闹铃时间为多少，样例保证必定有一个符合要求。
对闹铃排序，按照A从小到大排序，当A相同的时候，B从小到大排序，然后从最后一个往回遍历，找到距离上课时间>=Xmin中的闹铃时间，输出即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
/*
3
5 0
6 0
7 0
59
6 59
*/
using namespace std;
const int maxn=;
struct Node{
int h;
int m;
bool operator<(const Node tmp)const{
if(h==tmp.h)
return m<tmp.m;
else
return h<tmp.h;
}
};
Node clocks[maxn];
int n;
int main()
{
int a,b;
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d %d",&clocks[i].h,&clocks[i].m);
}
sort(clocks,clocks+n);
int x;
scanf("%d",&x);
scanf("%d %d",&a,&b);
for(int i=n-;i>=;i--){
if(clocks[i].h>a)
continue;
if(clocks[i].h==a){
if(b-clocks[i].m>=x){
printf("%d %d\n",clocks[i].h,clocks[i].m);
break;
}
}
else{
if(-clocks[i].m+(a-clocks[i].h-)*+b>=x){
printf("%d %d\n",clocks[i].h,clocks[i].m);
break;
}
}
} return ;
}
2. 离散化+二分查找
对于一个矩阵，在坐标系内，左下角坐标(x1,y1)，右上角坐标(x2,y2)，现在给出n个矩阵的坐标，问重叠区域矩阵最多的个数？如果没有矩阵重叠，输出1。
输入样例，第一行n，接下来分别为n个x1，n个y1，n个x2，n个y2。1<=n<=50，-10^9<=xi,yi<=10^9。
很明显，n的范围只有50，数据量很小，但是x和y很大，需要离散化处理，这样的话最多200个不同的值。
处理之后，对于第i个矩阵，遍历它所在的范围，cnt[i][j]++即可。最后输出cnt最大的那个。如果cnt都为0，即没有矩阵，也就没有重叠，也输出1。
这里注意，一开始我在遍历的时候，下面for循环，起始条件没有+1，这样的话还有10%样例是过不了的。应该是统计边，而不是统计点，因为对于[(0,0),(0,0)]是构不成矩阵的。
for(int k=lx+;k<=rx;k++){
for(int p=ly+;p<=ry;p++){
cnt[k][p]++;
}
}
完整代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
/*
2
0 90
0 90
100 200
100 200
*/
const int maxn=;
int n;
int xx1[maxn],xx2[maxn],yy1[maxn],yy2[maxn];
int idx=;
int a[maxn];
int hash_x[maxn];
int cnt[maxn][maxn]; int binarySearch(int *a,int t,int n){
int l=,r=n-;
int mid;
while(l<=r){
mid=(l+r)>>;
if(a[mid]==t)
return mid;
if(t<a[mid])
r=mid-;
else
l=mid+;
}
return -;
} int main()
{
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d",&xx1[i]);
a[i*+]=xx1[i];
}
for(int i=;i<n;i++){
scanf("%d",&yy1[i]);
a[i*+]=yy1[i];
}
for(int i=;i<n;i++){
scanf("%d",&xx2[i]);
a[i*+]=xx2[i];
}
for(int i=;i<n;i++){
scanf("%d",&yy2[i]);
a[i*+]=yy2[i];
}
//离散化，将-10^9~10^9的数据映射为0~200以内，因为最多出现4*50不同的数，映射值即为索引。
sort(a,a+*n);
hash_x[]=a[];
idx=;
for(int i=;i<*n;i++){
if(a[i]!=a[i-]){
hash_x[idx]=a[i];
idx++;
}
}
memset(cnt,,sizeof(cnt));
for(int i=;i<n;i++){
int lx,ly,rx,ry;
//二分查找对应离散化后的索引。
lx=binarySearch(hash_x,xx1[i],idx);
ly=binarySearch(hash_x,yy1[i],idx);
rx=binarySearch(hash_x,xx2[i],idx);
ry=binarySearch(hash_x,yy2[i],idx);
for(int k=lx+;k<=rx;k++){
for(int p=ly+;p<=ry;p++){
cnt[k][p]++;
}
}
}
int ans=;
for(int i=;i<=idx;i++){
for(int j=;j<=idx;j++){
ans=max(ans,cnt[i][j]);
}
}
if(ans==)
ans=;
printf("%d\n",ans);
return ;
}
3. dfs+剪枝
第一行n和w，接下来有n个零食的重量v[i]，0<v[i]<10^9，问你在背包重量为w的情况下，最多能有几种装法？背包重量为0也算一种。
比如说
3 8
1 2 3
因为总的背包容量大于三个总重量，所以三个每个都可选可不选，共计2^3种。
先对零食的重量从小到大排序，然后从最后一个开始，零食索引为idx，背包剩余容量为left，现有方案总数为tot，初始为0。
1. 若idx<=0或者left<=0，表示没得选了，只有就这一种方案，所以tot++即可。
2. 若idx之前所有零食的总重量<=left，那么很显然，该方案数总共为2^idx，加到tot上即可。
3. 若v[idx]<=left，那么我可以放第idx个零食，方案数即为dfs(idx-1,left-v[idx])。
4. 当然不管怎样，我也可以选择不放第idx个零食，方案数即为dfs(idx-1,left)。
注意，因为零食重量的范围，所以代码里的two数组、sum数组、tot为long long，才不会溢出，否则样例会有不过。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
const int maxn=;
int n;
int v[maxn];
long long sum[maxn]; //sum[i]统计v[1]~v[i]的和
int w;
long long tot=;
long long two[]; //two[i]即为2^i值 //dfs搜索所有的方案数
void dfs(int idx,int left){
if(idx<= || left<=){
tot+=;
return;
}
if(sum[idx]<=left){
tot+=two[idx];
return;
}
if(left>=v[idx]){
dfs(idx-,left-v[idx]);
}
dfs(idx-,left);
}
int main()
{
two[]=;
for(int i=;i<=;i++)
two[i]=two[i-]*;
scanf("%d %d",&n,&w);
for(int i=;i<=n;i++){
scanf("%d",&v[i]);
}
sort(v+,v+n+);
sum[]=;
for(int i=;i<=n;i++){
sum[i]=sum[i-]+v[i];
}
dfs(n,w);
printf("%lld\n",tot);
return ;
}