我要评论1.老鼠和猫的交易
#include<bits/stdc++.h>
using namespace std;
int i;
int m,n;//猫粮数，房间数
double tot=0;//换后的奶酪数
struct room{
double food;
double cheese;
}a[100000];//数组开大一点
//sort函数的函数部分，从大到小排序
bool cmp(room x,room y)
{
return (x.cheese)/x.food>(y.cheese)/y.food;
}
int main()
{
while(scanf("%d %d",&m,&n)!=eof)
{
if(m==-1&&n==-1) break;//结束条件
for(i=1;i<=n;i++)
cin>>a[i].cheese>>a[i].food;//读入奶酪和猫粮
sort(a+1,a+1+n,cmp);//注意首地址
for(i=1;i<=n;i++)
{
if(m-a[i].food>=0)//猫粮多于一只猫需要的猫粮
{
tot=tot+1.0*a[i].cheese;//老鼠得到奶酪增加
m=m-a[i].food;//老鼠手中猫粮减少
}
else//按比例购买最后一份猫粮
{
tot=tot+1.0*a[i].cheese/a[i].food*m;
break;
}
}
printf("%.3lf\n",tot);
tot=0;//注意结束后清零
}
return 0;
}2.田忌赛马
一篇非常详细的文章：http://t.csdnimg.cn/qqpsv
题目分析：田忌赛马是一种权衡取舍，找适合策略，来收获最大利益的问题。在本题中我们先将田忌与齐王的马进行排序（在此，我以降序排序），然后选择最优解（比较快马）：
1、田忌>齐王：正常比赛。
2、田忌<齐王：田忌慢马与齐王快马比赛。以慢换快
3、田忌=齐王（这一点十分容易忽略）：这时我们可以观察慢马，若此时田忌>齐王，可以直接让慢马比赛（无疑时必赢的）。若此时田忌<=齐王，将田忌慢马与齐王快马比赛（与慢马或快马进行比赛，都是不可能赢的，何不换取更大的利益）。
#include<bits/stdc++.h>
using namespace std;
//sort函数的函数部分，从大到小排序
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
int n,a[10000],b[10000];
while(scanf("%d",&n)!=eof)
{
if(n==0) break;
int i,j;
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<n;i++) cin>>b[i];
//从快到慢排序
sort(a,a+n,cmp);
sort(b,b+n,cmp);
int l1=0,l2=0,sum=0;//排序后的左侧快马
int r1=n-1,r2=n-1;//排序后的右侧慢马
for(i=0;i<n;i++)
{
if(a[l1]>b[l2])//快马：田忌 ＞齐王 ，正常比赛就可以赢
{
l1++;
l2++;
sum++;
}
else if(a[l1]<b[l2])//快马：田忌＜齐王 ，田忌慢马和齐王快马比赛，包输的
{
r1--;
l2++;
sum--;
}
else if(a[r1]>b[r2])//快马相等，慢马田忌＞齐王 ，正常比赛就赢了
{
r1--;
r2--;
sum++;
}
else if(a[r1]<b[l2])//快马相等，慢马田忌＜=齐王 ，田忌慢和齐王快比赛，包输的
{
r1--;
l2++;
sum--;
}
}
cout<<sum*200<<endl;
}
return 0;
}3.搬桌子
1. 我们可以把走廊模拟成一条线段，搬运桌子的起始位置模拟成这条线段上的区间；
2. 要想用时尽可能的少，我们应当让在同一时间段搬运的桌子尽可能多，也就是同一时间段线段上互不相交的区间尽可能多；
3. 对于那些存在重叠的区间，我们别无他法，只能分在不同时间段搬运；
4. 因此，我们需要找到区间之间的最大重叠次数，就是我们至少需要的时间；
注意点：由于房间分为两排，1和2, 3和4对应着同一段走廊，所以我们需要通过映射，把房间号对应成相应的走廊号。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,n,t,p[201];
int s,d,temp,k,max;
cin>>t;
while(t--)
{
for(i=0;i<=200;i++) p[i]=0;//初识化
cin>>n;
for(i=0;i<n;i++)
{
cin>>s>>d;
//使房间1和2对应的是一个位置
s=(s-1)/2;
d=(d-1)/2;
//从号码大的房间往回搬的情况
if(s>d)
{
temp=s;
s=d;
d=temp;
}
for(k=s;k<=d;k++) p[k]++;
}
max=-1;
for(i=0;i<=200;i++)
{
if(p[i]>max) max=p[i];//通过某个地方最大次数为最小时间
}
cout<<max*10<<endl;
}
return 0;
}4.今年暑假不ac
若干个电视节目，自样例：按结束时选择合适然要按时间顺序来看。为了看更多的节目，需要尽
快看完一个节目再看另外一个节目，多看短节目才能看更多的节目。
此题贪心的原则是，选择结束时间早的节目，留出时间看更多的节目。因此需要根据节目结束时间排序。
一开始，lastend=count=0，,循环i=0不对，然后改了一下，过了
#include<bits/stdc++.h>
using namespace std;
typedef struct node
{
int start;
int end;
}schedule;
bool cmp(schedule x,schedule y)
{
return x.end<y.end;
}
int main()
{
int i,n;
schedule s[100000];
while(scanf("%d",&n)!=eof)
{
if(n==0) break;
for(i=0;i<n;i++)
cin>>s[i].start>>s[i].end;
sort(s,s+n,cmp);
int lastend=s[0].end;
int count=1;
for(i=1;i<n;i++)
{
if(s[i].start>=lastend)
{
count++;
lastend=s[i].end;
}
}
cout<<count<<endl;
}
return 0;
}5.奋勇争先续
#include<bits/stdc++.h>
using namespace std;
struct stu
{
char name[100];
int num;
int time;
}s[1001];
bool com(stu a,stu b)
{
if(a.num<b.num) return a.num>b.num;//从大到小
else if(a.num==b.num) return a.time<b.time;//从小到大
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,i;
cin>>n>>m;
for(i=0;i<n;i++)
scanf("%s%d %d",s[i].name,&s[i].num,&s[i].time);
sort(s,s+n,com);
for(i=0;i<m;i++)
printf("%s %d %d\n",s[i].name,s[i].num,s[i].time);
printf("\n");
}
return 0;
} 6.degree sequence of graph g
可图性的问题
vector<int> a = {1,2,3};
sort(a.begin(), a.end(), greater<int>()); //将a降序排列
sort(a.begin(), a.end()); //将a升序排列
#include<bits/stdc++.h>
using namespace std;
int a[1006];
int havel(int n);
int main()
{
int t;
cin>>t;
while(t--)
{
int i,n,flag=0;
cin>>n;
for(i=0;i<n;i++) cin>>a[i];
if(havel(n)==1) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
int havel(int n)
{
int i,j;
for(i=0;i<n;i++)
{
sort(a,a+n,greater<int>());//降序排序
if(a[0]==0) return 1;//数组全0退出
for(j=1;j<=a[0];j++)
{
if(a[j]==0) return 0;//若为0，-1为负数无法构成简单图
else a[j]--;
}
a[0]=0;//当前点的度清零，会排在最后，不影响有度的点
}
}贪心算法：
在对问题求解时，总是作出在当前看来是最好的选择，也就是说，不从整体上加以考虑，所作出的仅仅是在某种意义上的局部最优解。
前提：排序。
最长的事件序列问题
可图性判定
1.度序列：若把图g所有顶点的度数排成一个序列s，则称s为图g的度序列。
2.序列是可图的：一个非负整数组成的有限序列如果是某个无向图的度序列，则称该序列是可图的。
havel-hakimi定理:,每趟都要排序。
sort函数
sort（首地址，尾地址+1，[cmp函数]）
1.这个函数可以传两个或三个参数
2.第一个参数是要排序的区间首地址
3.第二个参数是区间尾地址的下一地址
4.第三个参数不写，则缺省为递增排序
若为从大到小排序
int类型
int num[100];
bool cmp(int a,int b)
{
return a>b;
}
sort(num,num+100,cmp);结构体类型
struct node
{
int a;
double b;
}arr[100];
//先按照a值升序排列，若a值相同，再按b值降序排列。
bool cmp(node x,node y)
{
if(x.a!=y.a)
return x.a<y.a;
return x.b>y.b;
}
sort(arr,arr+100,cmp);浮点数比较大小不要直接==
double score；
if(fabs(x.score-y.score)>0.00001
return x.score>y.score;sort函数可以对数组的某一段进行排序。
若数组中元素是从下标1的位置开始存储，导致忘记修改sort的第一个参数。
发表评论