{"id":1105,"date":"2009-11-24T23:08:20","date_gmt":"2009-11-24T15:08:20","guid":{"rendered":"http:\/\/www.slyar.com\/blog\/?p=1105"},"modified":"2022-07-03T15:47:01","modified_gmt":"2022-07-03T22:47:01","slug":"poj-1754-c","status":"publish","type":"post","link":"http:\/\/www.slyar.com\/blog\/poj-1754-c.html","title":{"rendered":"POJ 1754 Buffer Manager C\u8bed\u8a00\u7248"},"content":{"rendered":"

\u6587\u7ae0\u4f5c\u8005\uff1a\u59dc\u5357(Slyar) <\/span>\u6587\u7ae0\u6765\u6e90\uff1aSlyar Home (www.slyar.com<\/a>) \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff0c\u8c22\u8c22\u5408\u4f5c\u3002<\/p>\n

\u7b80\u5355\u6a21\u62df\uff0c\u6211\u7528DP\u601d\u60f3\u505a\u4e86\u4e00\u6b21\u3002<\/p>\n

<\/p>\n

Description<\/span><\/p>\n

DBMS (Data Base Management System) development team has been successful in designing efficient Lock Manager and is going to proceed further. As a part of the team you will be responsible for the Buffer Manager.<\/p>\n

Data blocks being read by DBMS from the hard drive are stored in the main memory in a fixed number of pre-allocated buffers. Each buffer can hold one data block. Each buffer can be either free (does not contain any useful information) or occupied by some data. When DBMS is going to read data block from the hard drive it has to decide which buffer to use for data storing. If there are any free buffers, then one of them is used for that purpose. If there are no free buffers, then one of the occupied buffers has to be flushed to become free, unless it was locked by some part of DBMS.<\/p>\n

The choice of the buffer to flush is critical to DBMS performance. A lot of different algorithms were developed, LRU (Least Recently Used) algorithm being the one used most often. However, your DBMS is going to implement the Advanced Buffer Management algorithm which takes advantage of the fact that maximal performance is achieved when a number of consecutive data blocks from the hard drive are read into consecutive memory buffers.<\/p>\n

Buffers are numbered from 1 to N, where N (1 <= N <= 100000) is a total number of buffers. Each buffer can be in any one of the following states: free, occupied or locked. Each occupied buffer is assigned an integer number from 1 to 9 ? the worthiness of the currently stored information in that buffer. The worthiness of free buffers is considered to be zero. Locked buffers cannot be neither used nor flushed and their worthiness is undefined.<\/p>\n

Having received the request to read K (1 <= K <= 10000) data blocks from the hard drive, Buffer Manager has to choose K consecutive non-locked buffers numbered from L to L+K-1 that have minimal possible sum of their worthiness, or to report that it is impossible to find K consecutive non-locked buffers. The latter can also happen if total number of buffers is less than K.<\/p>\n

Your task is to write a program that models the processing of one request to Buffer Manager using the above algorithm.<\/p>\n

Input<\/span><\/p>\n

The first line of the input file contains two integers, N and K, separated by a space.<\/p>\n

Starting from the second line there is a description of a buffers' state. The state of each buffer is represented by a single character:<\/p>\n

* 0 - when the corresponding buffer is free.
\n* 1 - when the corresponding buffer is occupied and has worthiness of 1.
\n* 2 - when the corresponding buffer is occupied and has worthiness of 2.
\n* ...
\n* 9 - when the corresponding buffer is occupied and has worthiness of 9.
\n* * - when the corresponding buffer is locked.<\/p>\n

Those characters are situated on the consecutive lines grouped by 80 characters per line without any spaces. Thus, each line starting from the second one contains exactly 80 characters with a possible exception for the last line.<\/p>\n

Output<\/span><\/p>\n

Write to the output file the single integer number L. This number gives the buffer number where first of the K blocks from the hard drive shall be read to ensure the minimal possible total worthiness of the blocks that have to be flushed. If there are more than one such value for L, then write the smallest one.<\/p>\n

Write to the output file a single number 0 if it's impossible to find K consecutive non-locked buffers.<\/p>\n

Sample Input<\/span><\/p>\n

100 10
\n2165745216091853477755800393859785807207523169954341**7363*9*94664808*4777717089
\n09825185827659480548<\/p>\n

Sample Output<\/span><\/p>\n

36<\/p>\n

Slyar:\u5927\u610f\u5c31\u662f\u5728\u4e00\u4e2a\u957f\u5ea6\u4e3an\u7684\u6570\u5b57\u4e32\u4e2d\uff0c\u5bfb\u627e\u4e00\u4e2a\u957f\u4e3ak\u7684\uff0c\u4e0d\u5305\u542b'*'\u7684\uff0c\u52a0\u548c\u6700\u5c0f\u7684\u5b50\u4e32\u3002\u76f4\u63a5\u6a21\u62df\u5c31\u597d\u4e86\uff0c\u8bfb\u5165\u7684\u65f6\u5019\u6700\u597d\u7528%c\u4e00\u4e2a\u4e00\u4e2a\u8bfb\u3002\u505a\u5b8c\u4e4b\u540e\u611f\u89c9\u8fd9\u9898\u53ef\u4ee5\u7528DP\u601d\u60f3\uff0c\u5c1d\u8bd5\u7740\u641e\u4e86\u4e00\u4e0b\uff0c\u6ca1\u60f3\u5230\u8fd8\u771f\u8ba9\u6211\u5f04\u51fa\u6765\u4e86...<\/span><\/p>\n

\u7528F1[i]\u8868\u793a\u4ecei\u5230\u524d\u4e00\u4e2a'*'\u4e4b\u95f4\u6709\u591a\u5c11\u4e2a\u6570<\/span><\/p>\n

\u7528F2[i]\u8868\u793a\u4ecei\u5230\u524d\u4e00\u4e2a'*'\u4e4b\u95f4\u6240\u6709\u6570\u5b57\u7684\u52a0\u548c<\/span><\/p>\n

\u5bf9\u4e8e'*'\u6765\u8bf4\uff0cF1[i] = 0\uff0cF2[i] = 0<\/span><\/p>\n

\u5982\u679cF1[i] >= k\uff0c\u90a3\u4e48\u66f4\u65b0F2[i] - F2[i-k]\u7684\u6700\u4f18\u89e3<\/span><\/p>\n

\r\n#include \r\n\r\n#define SIZE 100010\r\n#define MAX 0x7fffffff\r\n\r\nint f1[SIZE] = {0};\r\nint f2[SIZE] = {0};\r\nint a[SIZE];\r\n\r\nint main()\r\n{\r\n    int i, j, n, k;\r\n    int pos, min, temp;\r\n    char ch;\r\n    scanf(\"%d%d\", &n, &k);\r\n    \r\n    min = MAX;\r\n    for (i = 1; i <= n; i++)\r\n    {\r\n        scanf(\"%c\", &ch);\r\n        if (ch == '\\n')\r\n        {\r\n            i--;\r\n        }\r\n        else if (ch == '*')\r\n        {\r\n            a[i] = -1;\r\n        }\r\n        else\r\n        {\r\n            a[i] = ch - '0';\r\n            f2[i] = f2[i-1] + a[i];\r\n            f1[i] = f1[i-1] + 1;\r\n            \/* \u66f4\u65b0\u6700\u4f18\u89e3 *\/\r\n            if (f1[i] >= k)\r\n            {\r\n                temp = f2[i] - f2[i-k];\r\n                if (temp < min)\r\n                {\r\n                    min = temp;\r\n                    pos = i - k + 1;\r\n                }\r\n            }\r\n        }\r\n    }\r\n    \r\n    if (min == MAX)\r\n    {\r\n        printf(\"0\\n\");\r\n    }\r\n    else\r\n    {\r\n        printf(\"%d\\n\", pos);\r\n    }\r\n    \r\n    \/\/system(\"pause\");\r\n    return 0;\r\n}\r\n<\/pre>\n
\u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff1aSlyar Home<\/a> » POJ 1754 Buffer Manager C\u8bed\u8a00\u7248<\/a><\/p>","protected":false},"excerpt":{"rendered":"
\u6587\u7ae0\u4f5c\u8005\uff1a\u59dc\u5357(Slyar) \u6587\u7ae0\u6765\u6e90\uff1aSlyar Home (www.slyar.com) \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff0c\u8c22\u8c22\u5408\u4f5c\u3002 \u7b80\u5355\u6a21\u62df\uff0c\u6211\u7528DP\u601d\u60f3\u505a\u4e86\u4e00\u6b21\u3002 \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff1aSlyar Home » POJ 1754 Buffer Manager  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1103],"tags":[1006],"class_list":["post-1105","post","type-post","status-publish","format-standard","hentry","category-acm-oj-solution","tag-poj"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t