北京建设电工证查询网站,电商网站怎样优化,响应式网站缺点,网络营销就是网站营销题目来源#xff1a;http://poj.org/problem?id1033 题目大意#xff1a; 某操作系统的文件系统中#xff0c;所有的磁盘空间被分为N个大小相等的cluster#xff0c;编号1至N。每个文件占用一个或多个cluster。所有没有被文件占用的cluster称为是空闲的。磁盘上的一个文件…题目来源http://poj.org/problem?id1033 题目大意 某操作系统的文件系统中所有的磁盘空间被分为N个大小相等的cluster编号1至N。每个文件占用一个或多个cluster。所有没有被文件占用的cluster称为是空闲的。磁盘上的一个文件如果放置在连续的cluster上读取速度是最快的。 磁盘以匀速旋转磁头找到某一个cluster的时间的不等的。因此找到靠近开头的cluster更快。所有的文件被事先按访问频率高到低编号1到K最好的文件放置方式是文件1放置于cluster 1,2,...S1文件2放置于cluster S11, S12,...S1S2.后面类似紧挨着放置。Si表示第i个文件占据的cluster数。 为了将磁盘上的文件整理成上述的最优放置方式需要对cluster进行移动。一次移动包括将一个cluster的内容读出来写至一块空闲的cluster上完成后之前的那块cluster变为空闲。 程序的目标是将磁盘上的文件变为最优放置方式需要的最少移动次数和移动次序。 输入第一行含两个整数N和K分别代表cluster数和文件数。接下来K行每行代表一个文件第一个数字代表该文件含多少cluster后面的每个数字代表所占的cluster的编号。 输出按顺序输出表示移动的数据对Pj,Qj。表示将Pj号cluster的数据移动到Qj.答案可能不唯一采用了Special Judge只要答案正确即可不需要移动则输出No optimization needed. Sample Input 20 3
4 2 3 11 12
1 7
3 18 5 10 Sample Output 2 1
3 2
11 3
12 4
18 6
10 8
5 20
7 5
20 7 实际上可以把问题看过一个数组的重新排列问题.用clusters[N]数组表示第i块cluster处放置的文件块的序号块的序号按重排后结果编排即该块最终应该位于哪一个cluster。那么重排后的结果应该是前面部分的clusters[i]i后面的部分clusters[i]0. 比如sample中的例子 初始状态 i: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 clusters[i]: 0 1 2 0 7 0 5 0 0 8 3 4 0 0 0 0 0 6 重排后 i: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 clusters[i]: 1 2 3 4 5 5 6 8 0 0 0 0 0 0 0 0 0 0 遍历所有的cluster会有以下几种情况 1. clusters[i]0不必处理。 2. clusters[i]1不必处理。 3. 不是以上两种情况则需要移动cluster。此时又有两种情况 a.需要移动的cluster形成链例如 i 1 2 3 4 5 6 clusters[i] 5 0 4 2 3 0 1被5占5被3占3被4占4被2占2为空。用栈保存占用关系借助一个空位逆向移动即可。 b.需要移动的cluster形成环例如 i 1 2 3 4 5 6 clusters 5 1 4 2 3 0 1被5占5被3占3被4占4被2占2又被1占。这种情况从磁盘末尾开始找一个空cluster(题目保证了一个至少有一个空的cluster否则就移动不了了)借助这个空的cluster然后逆向移动。 遍历完成时磁盘整理也完成了。 1 //2 // POJ1033 Defragment3 // Memory: 408K Time: 829MS4 // Language: C Result: Accepted5 //6 7 #include iostream8 #include stack9
10 using namespace std;
11
12 int main() {
13 int N;
14 int K;
15 int move_cnt 0;
16 cin N K;
17
18 int * clusters new int[N 1];
19 for (int i 0; i N; i) {
20 clusters[i] 0;
21 }
22 int sum 0;
23 for (int i 0; i K; i) {
24 int n;
25 cin n;
26 for (int j 1; j n; j) {
27 int a;
28 cin a;
29 clusters[a] sum;
30 }
31 }
32 for (int i 1; i N; i) {
33 if (clusters[i] 0 || clusters[i] i) {
34 continue;
35 }
36 stackint s;
37 int next clusters[i];
38 s.push(i);
39 bool isCircle false;
40 while (true) {
41 if (clusters[next] i) {
42 isCircle true;
43 break;
44 } else if (clusters[next] 0) {
45 break;
46 }
47 s.push(next);
48 next clusters[next];
49 }
50 if (isCircle true) {
51 int j N;
52 while (clusters[j] ! 0) {
53 --j;
54 continue;
55 }
56 cout next j endl;
57 clusters[j] clusters[next];
58 int t;
59 while (!s.empty()) {
60 t s.top();
61 cout t next endl;
62 clusters[next] clusters[t];
63 next t;
64 s.pop();
65 move_cnt;
66 }
67 clusters[next] clusters[j];
68 clusters[j] 0;
69 cout j next endl;
70 } else {
71 int t;
72 while (!s.empty()) {
73 t s.top();
74 cout t next endl;
75 clusters[next] clusters[t];
76 next t;
77 s.pop();
78 move_cnt;
79 }
80 clusters[next] 0;
81 }
82 }
83 if (move_cnt 0) {
84 cout No optimization needed endl;
85 }
86 system(pause);
87 return 0;
88 } View Code转载于:https://www.cnblogs.com/dengeven/p/3230223.html
