2018美團CodeM編程大賽 Round A Problem 2 下棋 【貪心】

應該一眼看出來是貪心題，然后想最優解是什么。正確的貪心策略是【原棋盤上每個位置的棋子】都往最近的左邊【目標棋盤上棋子】移動，如果左邊沒有棋子了那就閑置最后處理，如果目標棋盤在該位置上也有棋子，那就算距離為0（最近）。最后處理的話，棋盤上的局面應該是所有的棋子都得往右移，這樣的話怎么移都無所謂了，樸素的把放過去。

模擬的時候難度在于通過upper bound找到離該位置最近左的位置，所以復雜度是O(NlogN)；如果樸素的遍歷數組找最近左需要N復雜度，整體n^2就過不了了。

?

?對于upper_bound來說，返回的是被查序列中第一個大于查找值的指針，也就是返回指向被查值>查找值的最小指針，lower_bound則是返回的是被查序列中第一個大于等于查找值的指針，也就是返回指向被查值>=查找值的最小指針。 【引用自 https://blog.csdn.net/u011008379/article/details/50725670 】

?

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

int board[100005];
vector<int> va;
map<int,int> m;
long long ans;
//貪心策略
//每個都向自己最近的左邊的棋子移動
int main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>board[i];
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        if(x){//這個位置上有棋子
            va.push_back(i);
            m[i]=x;
        }
    }
    
    for(int i=1;i<=n;i++){
        while(1){
            vector<int>::iterator index = upper_bound(va.begin(),va.end(),i);/* index指向第一個大于i的元素 */
            //如果沒有比i還大的，返回begin()
            if(index==va.begin()) break;//目標盤左邊沒有棋子了 
            index--; 
            if( m[ *index ]>board[i] ) {
                ans+=(i-(*index) )*board[i];
                m[*index]-=board[i];
                board[i]=0;
                break;
            }
            if( m[ *index ]==board[i] ){
                ans+=(i-(*index))*board[i];
                va.erase(index);
                board[i]=0;
                break;
            }
            if( m[ *index]<board[i]){
                ans+=(i-(*index))*m[ *index];
                va.erase(index);
                board[i]-=m[*index];
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        if(board[i]==0) continue;
        while(1){
            if( m[ va[0] ]>board[i] ) {
                ans+=(i+va[0]-2)*board[i];
                m[ va[0] ]-=board[i];
                break;
            }
            if( m[ va[0] ]== board[i] ){
                ans+=(i+va[0]-2)*board[i];
                va.erase(va.begin());
                break;
            }
            if( m[ va[0] ]<board[i]){
                ans+=(i+va[0]-2)*m[ va[0] ];
                va.erase(va.begin());
                board[i]-=m[ va[0] ];
            }
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}

沒有提交在美團的oj上，但自己編了幾個數據都過了。