codeforces 1000 C [고전 제목] [정렬, 데이터 구조]

2947 단어 데이터 구조
아주 전형 적 인 문제 라 고 하 는데 저 는 처음 하 는 것 같 아 요. emmmm. 문 제 를 너무 적 게 하 는 것 같 아 요. 공부 가 너무 체계 적 이지 않 아 요.
제목 분석: n 개 구간 을 드 리 겠 습 니 다. 구간 에 겹 쳐 진 횟수 가 K 인 점 의 개수 가 몇 개 인지 물 어보 세 요. 각 k 가 [1... n] 에 속 하 는 점 의 개수 에 대해 서 는 그림 을 마음대로 그 려 보면 모든 점 을 정렬 한 다음 에 왼쪽 점 을 만나면 + 1, 오른쪽 점 을 만나면 - 1,이렇게 하면 우 리 는 각 구간 의 이때 커버 수 를 얻 을 수 있 습 니 다. 이렇게 모든 점 을 다 뛰 면 구간 을 구 할 수 있 습 니 다. 우리 가 주의해 야 할 것 은 오른쪽 점 을 기록 할 때 r + 1 로 계산 하면 구간 을 직접 포함 시 킬 수 있 습 니 다. 그러면 전체 점 에 대한 계산 을 간소화 할 수 있 습 니 다.
#include 
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=1e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef long long ll;
typedef pair E;
vectora;
ll ans[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    cl(ans);
    for(int i=1;i<=n;i++)
    {
        ll x,y;
        cin>>x>>y;
        a.push_back({x,1});
        a.push_back({y+1,-1});
    }
    sort(a.begin(),a.end());
    int now=0;
    for(int i=1;i1].second;
        ans[now]+=a[i].first-a[i-1].first;

    }
    for(int i=1;i<=n;i++)
    {
        cout<" ";
    }

    return 0;
}
[C 언어 데이터 구조 2] - 포인터 의 간단 한 복습
POJ 1875 Binary Search Heap Construction（treap）

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage