[USACO 2013 Jan B]Painting the fence

Java 解法, 执行用时: 496ms, 内存消耗: 23520K, 提交时间: 2023-07-23 22:45:56

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] distancePerMove = new int[n];
        //0 is open 1 is close

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            distancePerMove[i] = Integer.parseInt(st.nextToken());
            if(st.nextToken().charAt(0)=='L') {
                distancePerMove[i]*=-1;
            }
        }

        int[][] openClose = new int[n*2][2];
        int pos =0;
        for(int i=0; i<n*2; i++) {
            openClose[i][0] = pos;
            if(i%2==0) {
                pos += distancePerMove[i/2];
            }
        }

        for(int i=0; i<n; i++) {
            int temp1=openClose[i*2+1][0];
            int temp2 = openClose[i*2][0];
            openClose[i*2+1][0] = Math.max(temp2, temp1);
            openClose[i*2][0] = Math.min(temp2, temp1);
            openClose[i*2+1][1] = 1;
            openClose[i*2][1] = 0;
        }
        Arrays.sort(openClose, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        int ans = 0;
        int count = 0;
        for(int i=0; i<n*2; i++) {
            if(openClose[i][1]==0) {
                count++;
            } else {
                count--;
            }
            if(count>=2) {
                ans+=openClose[i+1][0]-openClose[i][0];
            }
        }

        bw.write(ans+"\n");
        bw.flush();
    }
}

C++14(g++5.4) 解法, 执行用时: 125ms, 内存消耗: 10104K, 提交时间: 2020-06-20 12:32:55

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[111111][2];
ll s[222222];
vector<ll>v;
map<ll,ll>m;
int main(){
    ll n,k,i,j;
    cin>>n;
    ll start=0;
    for(i=0;i<n;i++){
        ll x;
        char op;
        cin>>x>>op;
        if(op=='L'){
            a[i][0]=start-x;
            a[i][1]=start;
            start-=x;
        }
        else{
            a[i][0]=start;
            a[i][1]=start+x;
            start+=x;
        }
      //  cout<<a[i][0]<<" "<<a[i][1]<<endl;
        v.push_back(a[i][0]);
        v.push_back(a[i][1]);
    }
    sort(v.begin(),v.end());
    for(i=0;i<v.size();i++){
        m[v[i]]=i;
    }
    for(i=0;i<n;i++){
        s[m[a[i][0]]]++;
        s[m[a[i][1]]]--;
    }
    for(i=1;i<v.size();i++){
        s[i]+=s[i-1];
    }
    ll sum=0;
    for(i=0;i<v.size()-1;i++){
        //cout<<v[i]<<" "<<v[i+1]<<" "<<s[i]<<endl;
        if(s[i]>=2){

            sum+=v[i+1]-v[i];
        }
    }
    cout<<sum;
}

C++ 解法, 执行用时: 94ms, 内存消耗: 6564K, 提交时间: 2022-01-18 21:43:11

#include<bits/stdc++.h>
using namespace std;
#define ll int
ll a[111111][2];
ll s[222222];
vector<ll>v;
map<ll,ll>m;
int main(){
    ll n,k,i,j;
    cin>>n;
    ll start=0;
    for(i=0;i<n;i++){
        ll x;
        char op;
        cin>>x>>op;
        if(op=='L'){
            a[i][0]=start-x;
            a[i][1]=start;
            start-=x;
        }
        else{
            a[i][0]=start;
            a[i][1]=start+x;
            start+=x;
        }
      //  cout<<a[i][0]<<" "<<a[i][1]<<endl;
        v.push_back(a[i][0]);
        v.push_back(a[i][1]);
    }
    sort(v.begin(),v.end());
    for(i=0;i<v.size();i++){
        m[v[i]]=i;
    }
    for(i=0;i<n;i++){
        s[m[a[i][0]]]++;
        s[m[a[i][1]]]--;
    }
    for(i=1;i<v.size();i++){
        s[i]+=s[i-1];
    }
    ll sum=0;
    for(i=0;i<v.size();i++){
        //cout<<v[i]<<" "<<v[i+1]<<" "<<s[i]<<endl;
        if(s[i]>=2){

            sum+=v[i+1]-v[i];
        }
    }
    cout<<sum;
}

C++(g++ 7.5.0) 解法, 执行用时: 42ms, 内存消耗: 1956K, 提交时间: 2023-06-11 15:58:27

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
const int M=2e5;
const int mod=998244353;
const int INF=0x3f3f3f3f;
int n,m,k;
struct Node{
	int pos,f;	
	bool friend operator<(Node a,Node b){
		if(a.pos!=b.pos)return a.pos<b.pos;
		return a.f<b.f;
	}
}g[N+5];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;k=2;
	int pos=0;
	for(int i=1;i<=n;i++){
		int x;char ch[3];
		cin>>x>>ch;
		if(ch[0]=='L'){
			g[++m]=(Node){pos-x,1};
			g[++m]=(Node){pos,-1};
			pos-=x;
		}
		else{
			g[++m]=(Node){pos,1};
			g[++m]=(Node){pos+x,-1};
			pos+=x;
		}
	}
	sort(g+1,g+1+m);
	int ans=0,cur=0;
	for(int i=1;i<=m;i++){
		cur+=g[i].f;
		if(cur>=k)ans+=(g[i+1].pos-g[i].pos);
	}
	cout<<ans<<"\n";
	return 0;
}

详情