竹園論壇

標題: 39 - 餐廳評鑑 [打印本頁]

作者: ForTest    時間: 2014-4-23 13:32
標題: 39 - 餐廳評鑑
本帖最後由 ForTest 於 2014-4-23 13:46 編輯

題目:http://hoj.twbbs.org/judge/problem/view/39
AC Code:http://ideone.com/yhOc5k

今天我講的主題><
先照題目條件排序 接著做逆序數對
由於測資有點大 可是不想做離散化
所以code了Merge Sort做練習

Submission id:18647 Status:AC
http://hoj.twbbs.org/judge/judge/submission/18647
#include <iostream>
  • //#include <fstream>
  • #include <sstream>
  • #include <cstdio>
  • #include <cstring>
  • #include <string>
  • #include <cmath>
  • #include <algorithm>
  • //#include <map>
  • #include <stack>
  • #include <queue>
  • #include <vector>
  • //#include <deque>
  • #include <functional>
  • #include <ctime>
  • #include <cstdlib>
  • #include <iomanip>

  • using namespace std;
  • typedef long long LL;

  • #define F(a,b) for(int a=0;a<b;++a)

  • const int Max = 200001;

  • LL ans,k,m;;
  • pair<LL,LL> s[Max],tmp[Max];

  • void Count(int L,int M,int R){
  •     int i = L,j = M+1,pos = 0;
  •     while(i<=M && j<=R){
  •         if(s[i].first < s[j].first && s[i].second > s[j].second){
  •             tmp[pos++] = s[j++];
  •             ans += M - i + 1;
  •         }
  •         else tmp[pos++] = s[i++];
  •     }
  •     while(i <= M)tmp[pos++] = s[i++];
  •     while(j <= R)tmp[pos++] = s[j++];
  •     int now = 0;
  •     while(now < pos)s[L++] = tmp[now++];
  • }


  • void Divide(int L,int R){
  •     if(L == R)return;
  •     int M = (L+R)/2;
  •     Divide(L,M);
  •     Divide(M+1,R);
  •     Count(L,M,R);
  • }

  • int main(){
  •     while(~scanf("%lld%lld",&k,&m)){
  •         ans = 0;
  •         F(i,k)scanf("%lld",&s[i].first);
  •         F(i,k)scanf("%lld",&s[i].second);
  •         sort(s,s+k);
  •         Divide(0,(int)k-1);
  •         printf("%lld\n",ans);
  •     }
  • }










  • 歡迎光臨 竹園論壇 (http://forum.tfcis.org/) Powered by Discuz! X3.2