学做网站需要学那些程序,千库网素材免费下载官方,辽源网站建设,专业返利网站开发1.老鼠和猫的交易 小老鼠准备了M磅的猫粮#xff0c;准备去和看守仓库的猫做交易#xff0c;因为仓库里有小老鼠喜欢吃的五香豆。 仓库有N个房间#xff1b; 第i个房间有 J[i] 磅的五香豆#xff0c;并且需要用 F[i] 磅的猫粮去交换#xff1b; 老鼠不必交换该房间所有的五…1.老鼠和猫的交易 小老鼠准备了M磅的猫粮准备去和看守仓库的猫做交易因为仓库里有小老鼠喜欢吃的五香豆。 仓库有N个房间 第i个房间有 J[i] 磅的五香豆并且需要用 F[i] 磅的猫粮去交换 老鼠不必交换该房间所有的五香豆换句话说它可以用 F[i] * a% 磅的猫粮去换取 J[i] * a% 磅的五香豆其中a是一个实数。 现在请帮忙计算一下小老鼠最多能够得到多少磅的五香豆 输入描述 输入包含多组测试用例。 每组测试数据首先一行是2个非负整数 M 和 N 接着的 N 行每行分别包含2个非负整数 J[i] 和 F[i] 。 输入数据以两个-1结束。 题目保证所有的数据不超过1000。 输出描述 请计算并输出小老鼠最多能够得到的五香豆数量。 每组数据输出一行保留3位小数。 用例输入 1 5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1 用例输出 1 13.333
31.500 学习http://t.csdnimg.cn/gcmty
#includebits/stdc.h
using namespace std;
int i;
int m,n;//猫粮数房间数
double tot0;//换后的奶酪数
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-1n-1) break;//结束条件 for(i1;in;i)cina[i].cheesea[i].food;//读入奶酪和猫粮 sort(a1,a1n,cmp);//注意首地址 for(i1;in;i){if(m-a[i].food0)//猫粮多于一只猫需要的猫粮 {tottot1.0*a[i].cheese;//老鼠得到奶酪增加 mm-a[i].food;//老鼠手中猫粮减少 }else//按比例购买最后一份猫粮 {tottot1.0*a[i].cheese/a[i].food*m;break;} }printf(%.3lf\n,tot);tot0;//注意结束后清零 }return 0;
}
2.田忌赛马 “田忌赛马”是中国历史上一个著名的故事。 大约2300年前齐国大将田忌喜欢和国王赛马并且约定每赢一场对方就要付200元。 假设已知田忌和国王的各自马匹的速度都不相同请计算田忌最好的结果是什么。 输入描述 输入包含多组测试样例。 每组样例的第一行是一个整数n(n 1000),表示田忌和国王各自参赛的马匹数量。 接下来一行的n个整数表示田忌的马的速度再接下来一行的n个整数表示国王的马的速度。 n为0时表示输入数据的结束。 输出描述 每组数据输出一行表示田忌最多能够赢得的金额。 用例输入 1 3
92 83 71
95 87 74
2
20 19
22 18
0 用例输出 1 200
0 一篇非常详细的文章http://t.csdnimg.cn/qQPsV
题目分析田忌赛马是一种权衡取舍找适合策略来收获最大利益的问题。在本题中我们先将田忌与齐王的马进行排序在此我以降序排序然后选择最优解比较快马
1、田忌齐王正常比赛。
2、田忌齐王田忌慢马与齐王快马比赛。以慢换快
3、田忌齐王这一点十分容易忽略这时我们可以观察慢马若此时田忌齐王可以直接让慢马比赛无疑时必赢的。若此时田忌齐王将田忌慢马与齐王快马比赛与慢马或快马进行比赛都是不可能赢的何不换取更大的利益。
#includebits/stdc.h
using namespace std;//sort函数的函数部分从大到小排序
bool cmp(int x,int y)
{return xy;
}int main()
{int n,a[10000],b[10000];while(scanf(%d,n)!EOF){if(n0) break; int i,j;for(i0;in;i) cina[i];for(i0;in;i) cinb[i];//从快到慢排序 sort(a,an,cmp);sort(b,bn,cmp);int l10,l20,sum0;//排序后的左侧快马 int r1n-1,r2n-1;//排序后的右侧慢马 for(i0;in;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--;}}coutsum*200endl;}return 0;
}
3.搬桌子 丁爸信奥培训中心最近在富丽科技大厦租了一层楼这层楼的形状如下 由图可见这层楼中间是走廊两侧各有200个房间编号如上图。 最近丁爸信奥培训中心做了内部机构的调整需要把一些桌子从一个房间搬到另外的房间。因为走廊很窄但是桌子很大所以同一段走廊每次只能通过一个桌子。 假设不论远近每趟搬桌子都需要10分钟。同时当你从房间i搬桌子到房间j的过程中房间i到房间j之间的走廊都被占用也就是说在每个10分钟内不能有多个任务共享同一段走廊。 现在丁爸想知道要完成所有的搬运任务最少需要多少时间 输入描述 输入包含T组测试用例。 每组测试用例首先是一个正整数N1N200表示需要搬运的桌子数量。 接下来N行每行包含2个正整数s和t,表示需要将一个桌子从房间s搬到房间t。 输出描述 计算并输出完成所有的搬运任务需要的最少的时间每组数据占一行。 用例输入 1 3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50 用例输出 1 10
20
30 1. 我们可以把走廊模拟成一条线段搬运桌子的起始位置模拟成这条线段上的区间
2. 要想用时尽可能的少我们应当让在同一时间段搬运的桌子尽可能多也就是同一时间段线段上互不相交的区间尽可能多
3. 对于那些存在重叠的区间我们别无他法只能分在不同时间段搬运
4. 因此我们需要找到区间之间的最大重叠次数就是我们至少需要的时间
注意点由于房间分为两排1和2, 3和4对应着同一段走廊所以我们需要通过映射把房间号对应成相应的走廊号。
#includebits/stdc.h
using namespace std;
int main()
{int i,j,n,t,p[201];int s,d,temp,k,max;cint;while(t--){for(i0;i200;i) p[i]0;//初识化 cinn;for(i0;in;i){cinsd;//使房间1和2对应的是一个位置 s(s-1)/2;d(d-1)/2;//从号码大的房间往回搬的情况if(sd) {temps;sd;dtemp;}for(ks;kd;k) p[k];}max-1;for(i0;i200;i){if(p[i]max) maxp[i];//通过某个地方最大次数为最小时间 }coutmax*10endl;} return 0;
}
4.今年暑假不AC 作为球迷一定想看尽量多的完整的比赛当然作为新时代的好青年你一定还会看一些其它的节目比如新闻联播永远不要忘记关心国家大事、非常67、超级女生以及王小丫的《开心辞典》等等假设你已经知道了所有你喜欢看的电视节目的转播时间表你会合理安排吗目标是能看尽量多的完整节目 输入描述 输入数据包含多个测试实例每个测试实例的第一行只有一个整数n(n100)表示你喜欢看的节目的总数然后是n行数据每行包括两个数据Tis,Tie (1in)分别表示第i个节目的开始和结束时间为了简化问题每个时间都用一个正整数表示。n0表示输入结束不做处理。 输出描述 对于每个测试实例输出能完整看到的电视节目的个数每个测试实例的输出占一行。 用例输入 1 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 用例输出 1 5 若干个电视节目自样例按结束时选择合适然要按时间顺序来看。为了看更多的节目需要尽 快看完一个节目再看另外一个节目多看短节目才能看更多的节目。 此题贪心的原则是选择结束时间早的节目留出时间看更多的节目。因此需要根据节目结束时间排序。
一开始lastendcount0,循环i0不对然后改了一下过了
#includebits/stdc.h
using namespace std;
typedef struct node
{int start;int end;
}schedule;bool cmp(schedule x,schedule y)
{return x.endy.end;
}int main()
{int i,n;schedule s[100000];while(scanf(%d,n)!EOF){if(n0) break;for(i0;in;i)cins[i].starts[i].end;sort(s,sn,cmp);int lastends[0].end;int count1;for(i1;in;i){if(s[i].startlastend){count;lastends[i].end;}}coutcountendl;}return 0;
}
5.奋勇争先续 还记得上次那个奋勇争先的题目吗聪明的你帮助老师找出了第一名的同学。 现在有个类似的问题 已知每一位同学的解题数量和罚时这次希望你能输出排名靠前的若干同学的名单。 注排名首先依据做题数量若做题数量相同则比较罚时罚时少的排名靠前。 输入描述 第一行是数据组数C代表有C组测试实例。 每一组数据第一行两个整数N和MN代表有N个人的成绩M表示老师需要你输出前M名的名单。 接下来N行每一行依次给出名字Name做出的题目数量num和罚时time ( 1C10, 2MN1000, Name的长度最大为101num10 10time100000 ) 输出描述 每组测试数据输出M行第i行为第i名的名字、解题数量和罚时中间用空格隔开。 每组数据后空一行。 用例输入 1 1
3 3
Bob 5 50
Alice 4 46
John 5 48 用例输出 1 John 5 48
Bob 5 50
Alice 4 46 #includebits/stdc.h
using namespace std;
struct stu
{char name[100];int num;int time;
}s[1001];bool com(stu a,stu b)
{if(a.numb.num) return a.numb.num;//从大到小else if(a.numb.num) return a.timeb.time;//从小到大
}int main()
{int t;cint;while(t--){int n,m,i;cinnm;for(i0;in;i)scanf(%s%d %d,s[i].name,s[i].num,s[i].time);sort(s,sn,com);for(i0;im;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 Wang Haiyang is a strong and optimistic Chinese youngster. Although born and brought up in the northern inland city Harbin, he has deep love and yearns for the boundless oceans. After graduation, he came to a coastal city and got a job in a marine transportation company. There, he held a position as a navigator in a freighter and began his new life. The cargo vessel, Wang Haiyang worked on, sails among 6 ports between which exist 9 routes. At the first sight of his navigation chart, the 6 ports and 9 routes on it reminded him of Graph Theory that he studied in class at university. In the way that Leonhard Euler solved The Seven Bridges of Knoigsberg, Wang Haiyang regarded the navigation chart as a graph of Graph Theory. He considered the 6 ports as 6 nodes and 9 routes as 9 edges of the graph. The graph is illustrated as below. According to Graph Theory, the number of edges related to a node is defined as Degree number of this node. Wang Haiyang looked at the graph and thought, If arranged, the Degree numbers of all nodes of graph G can form such a sequence: 4, 4, 3,3,2,2, which is called the degree sequence of the graph. Of course, the degree sequence of any simple graph (according to Graph Theory, a graph without any parallel edge or ring is a simple graph) is a non-negative integer sequence? Wang Haiyang is a thoughtful person and tends to think deeply over any scientific problem that grabs his interest. So as usual, he also gave this problem further thought, As we know, any a simple graph always corresponds with a non-negative integer sequence. But whether a non-negative integer sequence always corresponds with the degree sequence of a simple graph? That is, if given a non-negative integer sequence, are we sure that we can draw a simple graph according to it.? Let’s put forward such a definition: provided that a non-negative integer sequence is the degree sequence of a graph without any parallel edge or ring, that is, a simple graph, the sequence is draw-possible, otherwise, non-draw-possible. Now the problem faced with Wang Haiyang is how to test whether a non-negative integer sequence is draw-possible or not. Since Wang Haiyang hasn’t studied Algorithm Design course, it is difficult for him to solve such a problem. Can you help him? 输入描述 The first line of input contains an integer T, indicates the number of test cases. In each case, there are n1 numbers; first is an integer n (n1000), which indicates there are n integers in the sequence; then follow n integers, which indicate the numbers of the degree sequence. 输出描述 For each case, the answer should be yesor “no” indicating this case is “draw-possible” or “non-draw-possible”. 用例输入 1 2
6 4 4 3 3 2 2
4 2 1 1 1 用例输出 1 yes
no 可图性的问题 sort()函数中的greaterint()参数表示将容器内的元素降序排列。不填此参数默认表示升序排列。 vectorint a {1,2,3};
sort(a.begin(), a.end(), greaterint()); //将a降序排列
sort(a.begin(), a.end()); //将a升序排列学习http://t.csdnimg.cn/ENfbk
#includebits/stdc.h
using namespace std;
int a[1006];int havel(int n);int main()
{int t;cint;while(t--){int i,n,flag0;cinn;for(i0;in;i) cina[i];if(havel(n)1) coutyesendl;else coutnoendl;}return 0;
} int havel(int n)
{int i,j;for(i0;in;i){sort(a,an,greaterint());//降序排序 if(a[0]0) return 1;//数组全0退出 for(j1;ja[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 ab;
}
sort(num,num100,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.ay.a;return x.by.b;
}
sort(arr,arr100,cmp);
浮点数比较大小不要直接
double score
if(fabs(x.score-y.score)0.00001return x.scorey.score;
sort函数可以对数组的某一段进行排序。
若数组中元素是从下标1的位置开始存储导致忘记修改sort的第一个参数。
