原題目

?

A Magic Lamp

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3964????Accepted Submission(s): 1605

Problem Description Kiki likes traveling. One day she finds a magic lamp, unfortunately the genie in the lamp is not so kind. Kiki must answer a question, and then the genie will realize one of her dreams.?
The question is: give you an integer, you are allowed to delete exactly m digits. The left digits will form a new integer. You should make it minimum.
You are not allowed to change the order of the digits. Now can you help Kiki to realize her dream?

?

Input There are several test cases.
Each test case will contain an integer you are given (which may at most contains 1000 digits.) and the integer m (if the integer contains n digits, m will not bigger then n). The given integer will not contain leading zero.

?

Output For each case, output the minimum result you can get in one line.
If the result contains leading zero, ignore it.?

?

Sample Input 178543 4 1000001 1 100001 2 12345 2 54321 2

?

Sample Output 13 1 0 123 321

?

?

********************************************************************************************************************************************************************************************

題意：給你一個數字串 （每一個串有n個數字）， 和一個m （要你刪除m個數字 )， 使得剩下的數字組成的整數最小。

一開始想了一下刪除m個，等價與在數字串中選擇 n-m 個數字組成最小整數。

一開始一直做不出，貪心有點問題。后來被dalao教一下就懂了；

貪心的方法：

我們先假設 n 是串的個數， m 是要刪除的個數， need 是需要選的個數；

1） 因為是按照順序組合數字的， 所以第一個刪除的數字一定在 ?[0, n-need] 之內；

證明： 假設數字有 a0, a1, a2, a3, a4, a5 個，要刪除2個，n=6, m=2, need = 4;

因為是連續選擇的，我們假設在 [0, 3]之內選擇第一個，那么我們只剩下a4, a5了，無法構成4個；

所以假設最后的need-1個我們都要， 那么 從?0 ~ (n - 1) - ( need - 1 )==[0, n-need]之內第一個一定在里面（數組從0開始，所以 n-1）;

2） 當在[0, n-need]之內選好了第一個，找到第一個的位置pre，那么下一個 數字一定在 [ pre + 1, n-need + 1 ]， 就可以一直找下去了，記錄你找到的數；

3） 最后在你找到的數里面討論前導0的情況。

?

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <vector> 6 #include <deque> 7 using namespace std; 8 const int maxn = 1000+10; 9 int d[maxn][maxn]; 10 int a[maxn]; 11 void RMQ_init(string s) 12 { 13 memset(d, 0, sizeof(d)); 14 memset(a, 0, sizeof(a)); 15 int n = s.size(); 16 for(int i=0;i< n ;i++) a[i]=d[i][0]=s[i]-'0'; 17 for(int j = 1; (1<<j) <= n ;j++) 18 for(int i = 0 ; i+(1<<j ) -1 < n ;i++) 19 d[i][j] = min(d[i][j-1] , d[i+(1<<(j-1))][j-1] ); 20 } 21 int RMQ(int L, int R) 22 { 23 int k=0; 24 while((1<<(k+1)) <= R-L+1) k++; 25 return min(d[L][k], d[R-(1<<k) + 1][k]); 26 } 27 int findmin(int L, int R, int Min) 28 { 29 for(int i=L; i <= R ;i++){ 30 if(a[i] == Min) return i; 31 } 32 } 33 int main() 34 { 35 string s; 36 int m, n, need; 37 while(cin >> s >> m){ 38 RMQ_init(s); 39 n = s.size() ; 40 need = n - m; 41 int Left=0, Right = n - need; 42 // cout << Left << " " << Right << endl; 43 // cout << RMQ(Left, Right) << endl; 44 deque <int > q; 45 while(1){ 46 if(need ==0 ) break; 47 int Min = RMQ(Left, Right); 48 // cout << Min << endl; 49 q.push_back(Min); 50 int pre = findmin(Left, Right, Min); 51 Left = pre+1; 52 Right ++ ; 53 need --; 54 } 55 while(!q.empty()){ 56 if(q.front() == 0) q.pop_front(); 57 else break; 58 } 59 if(q.empty()){ 60 cout << "0"; 61 } 62 else{ 63 while(!q.empty()){ 64 cout << q.front(); 65 q.pop_front(); 66 } 67 } 68 cout << endl; 69 } 70 return 0; 71 }

?

轉載于:https://www.cnblogs.com/denghaiquan/p/6666168.html

總結

以上是生活随笔為你收集整理的HDU 3183 A Magic Lamp(RMQ问题， ST算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。