這兩天做了幾道水題練練這些基本的東西。

題目都很簡單。

我忘記在什麼地方看到過有個人說過：有些人認為貪心不總能求出最優解，所以所貪心沒用，高手與菜鳥的區別就體現在這裡。貪心用的好的一般都是大神。

所以以後要注意貪心了。

 

Wooden Sticks

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10885 Accepted Submission(s): 4487


Problem Description There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l<=l' and w<=w'. Otherwise, it will need 1 minute for setup.

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

Input The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains n 2 positive integers l1, w1, l2, w2, ..., ln, wn, each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

Output The output should contain the minimum setup time in minutes, one per line.

Sample Input

3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

Sample Output

2
1
3

這個題因為我搜的題的時候作者就說了這是貪心的題目，我也沒多想，就寫了。反正對我來說能學到東西。

 

因為這個處理的中間過程的時候，還出錯了。

思路用該很簡單，就是先排序，按照長度，長度相同按寬度排序。

調用的c++函數，很快。

最好自己寫排序函數，因為我都是調用函數，所以現在讓我寫快排什麼的 應該很費勁甚至寫不出來。

長度有序了，那就不用管了。接下來我們只處理寬度就行了。

一遍一遍的遍歷。遍歷一遍就是結果+1，在遍歷過程中 ，把這次能夠處理的全部標記上已經處理了，下次就不用管了。

最後看看遍歷了幾次都處理了就行了。

貼上代碼。

 

#include 
#include 
#include 
using namespace std;

struct Point
{
    int l;
    int w;
};

bool comp(Point a,Point b )
{
    if(a.l!=b.l)
    {
        return a.l>cases;
    while(cases--)
    {
        int n;
        cin>>n;
        Point p[5001];
        for(int i=0;i>p[i].l;
            cin>>p[i].w;
        }
        sort(p,p+n,comp);
        int m=0,t=0;
        bool b[5001];
        int ans=0;
        memset(b,false,sizeof(b));
        while(m=t)
                {
                    m++;
                    b[j]=true;
                    t=p[j].w;
                }
            }
        }
        cout<

代碼簡單易懂，我用結構體存儲的木棒，用bool數組來標記是否處理過了。用m來表示當前已經處理多少元素了，如果處理元素和輸入個數相同了，那麼while結束。
 
t就是當前處理的寬度，下次只能處理比當前這次寬的。
好了！
感謝自己堅持。