Bài toán gieo hạt

bài này theo mình thì dùng 2 biến L R và 1 biến G là xong. Chả biết có đúng không. Đây là code mình viết bằng C++
http://ideone.com/dPaQhS

Giải thuật
Bài này khá đơn giản.
Quy ước vị trí ban đầu của người đó là 0, khi qua trái vị trí người đó sẽ giảm, khi qua phải, vị trí người đó sẽ tăng. Ta cần xác định hai vị trị tận cùng mà người đó đến được từ đó suy ra đáp số bài toán.
Code:

//code by tamlien
#include <iostream>
using namespace std;

int main()
{
    int n, cur=0, posMin=2147483647, posMax=-posMin;// khởi tạo các giá trị ban đầu.
    cin>>n;
    char Type;
    int x;
    for(int i=0; i<n; i++)
    {
        cin>>Type>>x;
        if(Type=='L') cur-=x;
        else cur+=x;
        if(cur>posMax) posMax=cur; // tối ưu lại....
        if(cur<posMin) posMin=cur;
    }
    cout<<posMax-posMin;
    return 0;
}

giaosudauto.blogspot.com

giaosudauto

Giaosudauto Hacker Blogger

Hehe, đề gốc có ở phần Update nhé. Các bạn tiếp tục giải nhé.

Rời rạc hoá các điểm thì sẽ có không quá 2000 đầu mút
Dùng 1 mảng đánh dấu A, các dòng input=> (x,y)
Thì mảng đánh dấu A[x]+=1; A[y+1]-=1;
Sau đó cộng dồn thì biết dc khoảng nào gieo bao nhiêu lần

Good idea …

Nhưng mà số cánh đồng ở đây là 10^9 thì nó có chạy nổi trong 1s không?

Code thử

#include <bits/stdc++.h>
using namespace std;


const int maxn = 2e3+10;

typedef long long ll;
int A[maxn];
ll rev[maxn];

int main() {
    
    int cur=0,next;
    string a;
    int dst;
    vector<pair<ll,ll> > vt;
    while(cin>>a>>dst){
        
        if(a=="L"){
            next=cur-dst;
        }else{
            next=cur+dst;
        }
        vt.push_back(make_pair(min(cur,next),max(cur,next)));
        cur=next;
    }
    // roi rac hoa
    map<ll,int> m;
    for(auto p: vt){
        m[p.first]=1;
        m[p.second]=1;
    }
    int cnt=1;
    for(auto &p: m){
        rev[cnt]=p.first;
        p.second=cnt++;
    }
    //for(auto p: m){
    //    cout<<p.first<<" "<<p.second<<endl;
    //}
    fill(A,A+m.size()+1,0);
    for(auto p: vt){
        A[m[p.first]]++;
        A[m[p.second]+1]--;
    }
    for(int i=1;i<=m.size();i++){
        A[i]+=A[i-1];
    }
    
    for(int i=1;i<m.size();i++){
        cout<<rev[i]<<" "<<rev[i+1]<<" "<<A[i]<<endl;
    }
    
    return 0;
}