P1496 burning red cliff

Title:

After Cao Cao pacified the north, in 208 ad, he led a large army to the South and attacked Liu Biao. Liu Biao died before his men and horses arrived in Jingzhou. Liu Cong, his son, was frightened by Cao's powerful voice and sent for surrender.

Sun Quan appointed Zhou Yu as the governor and assigned him 30000 sailors to fight against Cao Cao with Liu Bei.

In November in the middle of winter, the weather suddenly warmed up and there was a southeast wind.

Unexpectedly, the east Wu fleet was about two miles away from the north bank, and ten big ships in front of it suddenly caught fire at the same time. Fire takes advantage of wind and wind helps fire. Ten fire boats, like ten fire dragons, break into Cao Jun's water stronghold. The ships there were all crowded together, unable to hide, and soon burned. In a blink of an eye, a sea of fire had been set on fire.

Cao Cao was so angry that he found you and asked you to drill into the sea of fire and count the length of the burning ships on the chain!

Input format

The first line is an integer N.

In the next N lines, there are two numbers in each line: A[i], B[i], indicating the starting position and ending point of the ship on the catenary.

Output format

Output the total length of the vessel on fire. Ensure that the answer is in the range of 32-bit signed integers.

Example of input and output

Input #1:

3
-1 1
5 11
2 9

Output #1:

11

Description / tips

0<n<20000 -2147483648<a[i],b[i]<2147483648
————————————Here's how to start parsing -————————————

Method 1:

If there is no negative number in this question

It will be very simple

Enter two numbers at a time

From f[a[i]] to f[b[i]]

All assigned to 1

(initial value is 0)

If there are negative numbers

Just another array

Used to handle negative numbers

1.0 code is attached below

#include<bits/stdc++.h>
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
struct cina
{
    int a;
    int b;
};
cina c[10001];
int n,sum,zd[1000001],fd[1000001];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>c[i].a>>c[i].b;
    for(int i=1;i<=n;i++)
    {
        if(c[i].a<0)
        {
            if(c[i].b<0)
            {
                for(int j=c[i].a;j<=c[i].b;j++)
                {
                    if(fd[-j]!=0)
                    {
                        fd[-j]=0;
                        sum++;
                    }
                }
            }//If it's all negative
            else
            {
                for(int j=c[i].a;j<=-1;j++)
                {
                    if(fd[-j]!=0)
                    {
                        fd[-j]=0;
                        sum++;
                    }
                }
                for(int j=0;j<=c[i].b;j++)
                {
                    if(zd[j]!=0)
                    {
                        zd[j]=0;
                        sum++;
                    }
                }
            }//If the former is a negative number, the latter is a positive number
        }
        else
        {
            for(int j=c[i].a;j<=c[i].b;j++)
            {
                if(zd[j]!=0)
                {
                    zd[j]=0;
                    sum++;
                }
            }
        }//This paragraph is all positive
    }
    cout<<sum<<endl;
    return 0;
}

however

This question has a wide range of data

Array cannot be too large

therefore

This method

Don't rely on it!

Method 2:

After entering

All variables are sorted first

Then it is divided into the following three schemes:

1. If a[i] is less than b[i-1] and b[i] is greater than b[i-1]
ans+=b[i]-b[i-1];
2. If both a[i] and b[i] are smaller than b[i-1]
ans unchanged
3. If both a[i] and b[i] are greater than b[i-1]
ans+=b[i]-a[i]

Here is the 2.0 code

#include<bits/stdc++.h>
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,a[20001],b[20001],sum,temp,R;
//bool flag=true;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=n-1;i++)
    {
    	for(int j=1;j<=n-i;j++)
    	{
  		  	if(a[j]>a[j+1])  
   			{
   		  		temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
				temp=b[j];
				b[j]=b[j+1];
				b[j+1]=temp;//b array also changes
   		 	}
		}
	}//sort
	
	//for(int i=1;i<=n;i++) cout<<a[i]<<" "<<b[i]<<endl;
	
	sum=b[1]-a[1];
	R=b[1];
	if(n==1)
	{
		cout<<sum<<endl;
		return 0;
	}
	for(int i=2;i<=n;i++)
	{
		if(a[i]<R) 
		{
			if(b[i]<=R) continue;//Option 2
			else
			{
				sum+=b[i]-R;
				R=b[i];
				continue;
			}//Option 1
		}
		else 
		{
			sum+=b[i]-a[i];
			R=b[i];
		}//Option 3
	}
    cout<<sum<<endl;
    return 0;
}

You will find

First test point

Overtime

The solution is

Change bubble sort to selective sort

Here is the 3.0 code

#include<bits/stdc++.h>
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,a[20001],b[20001],sum,temp,R;
bool flag=true;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    for (int i=1;i<=n-1;i++)            
    {
        int k=i;
        for(int j=i+1;j<=n;j++)      
        if(a[j]<a[k])  k=j;
        if(k!=i)                             
        { 
             temp = a[i];
             a[i] = a[k]; 
             a[k] = temp; 
             temp=b[i];
             b[i]=b[k];
            b[k]=temp;
        }
    }//Changed to select sort
	sum=b[1]-a[1];
	R=b[1];
	if(n==1)
	{
		cout<<sum<<endl;
		return 0;
	}
	for(int i=2;i<=n;i++)
	{
		if(a[i]<R) 
		{
			if(b[i]<=R)
				continue;
			else
			{
				sum+=b[i]-R;
				R=b[i];
				continue;
			}
		}
		else 
		{
			sum+=b[i]-a[i];
			R=b[i];
		}
	}
    cout<<sum<<endl;
    return 0;
}

Finally passed!!!