二分 – Page 2 – hahaschool

POJ 3258 River Hopscotch

January 20, 20152015-01-20hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <stack>

using namespace std;

int main(){
    int l = 0,n = 0,m = 0;
    vector<int> rock;
    while (cin >> l >> n >> m) {
        for (int i = 1; i <= n; i++) {
            int tmp;
            scanf(" %d",&tmp);
            rock.push_back(tmp);
        }
        rock.push_back(l);
        rock.push_back(0);
        sort(rock.begin(), rock.end());

        int high = l,low = 0,mid = l/2;
        int ans = 0;
        while (high >= low) {
            mid = (high+low)/2;
            int cnt = 0,prev = 0;
            for (int i = 1; i < rock.size(); i++) {
                if (rock[i] - rock[prev] < mid) {
                    cnt++;
                }else {
                    prev = i;
                }
            }

            if (cnt > m) {
                high = mid-1;
            }else{
                ans = mid;
                low = mid+1;
            }
        }
        cout << ans << endl;
    }



    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <stack>

using namespace std;

int main(){

int l = 0,n = 0,m = 0;

vector<int> rock;

while (cin >> l >> n >> m) {

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

int tmp;

scanf(" %d",&tmp);

rock.push_back(tmp);

}

rock.push_back(l);

rock.push_back(0);

sort(rock.begin(), rock.end());

int high = l,low = 0,mid = l/2;

int ans = 0;

while (high >= low) {

mid = (high+low)/2;

int cnt = 0,prev = 0;

for (int i = 1; i < rock.size(); i++) {

if (rock[i] - rock[prev] < mid) {

cnt++;

}else {

prev = i;

}

if (cnt > m) {

high = mid-1;

}else{

ans = mid;

low = mid+1;

}

cout << ans << endl;

}

return 0;

}

二分不会啊。。。

POJ 2299 Ultra-QuickSort

January 20, 20152015-01-20hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <stack>

using namespace std;

#define INFINITE 1000000005

long long swapt = 0;
void merge(int* a,int start,int mid,int end){
    long long swaptimes = 0;
    vector<int> larr,rarr;
    for (int i = start; i <= mid; i++) {
        larr.push_back(a[i]);
    }
    larr.push_back(INFINITE);
    for (int i = mid+1; i <= end; i++) {
        rarr.push_back(a[i]);
    }
    rarr.push_back(INFINITE);
    int lcur = 0,rcur = 0;
    for (int cur = start; cur <= end; cur++) {
        if (larr[lcur] < rarr[rcur]) {
            a[cur] = larr[lcur];
            swaptimes += abs(lcur - cur + start);
            lcur++;
            continue;
        }else{
            a[cur] = rarr[rcur];
            swaptimes += abs(rcur + mid + 1 - cur);
            rcur++;
            continue;
        }
    }
    swapt += swaptimes/2;
}
void mergesrt(int* a,int start,int end){
    int mid = (start+end)/2;
    if (start < end) {
        mergesrt(a, start, mid);
        mergesrt(a, mid+1, end);
        merge(a,start,mid,end);
    }
}

int main(){
    int n = 0;
    int seq[500005];
    while (cin >> n && n) {
        swapt = 0;
        for (int i = 0; i < n; i++) {
            scanf(" %d",&seq[i]);
        }
        mergesrt(seq, 0, n-1);
        cout << swapt << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <stack>

using namespace std;

#define INFINITE 1000000005

long long swapt = 0;

void merge(int* a,int start,int mid,int end){

long long swaptimes = 0;

vector<int> larr,rarr;

for (int i = start; i <= mid; i++) {

larr.push_back(a[i]);

}

larr.push_back(INFINITE);

for (int i = mid+1; i <= end; i++) {

rarr.push_back(a[i]);

}

rarr.push_back(INFINITE);

int lcur = 0,rcur = 0;

for (int cur = start; cur <= end; cur++) {

if (larr[lcur] < rarr[rcur]) {

a[cur] = larr[lcur];

swaptimes += abs(lcur - cur + start);

lcur++;

continue;

}else{

a[cur] = rarr[rcur];

swaptimes += abs(rcur + mid + 1 - cur);

rcur++;

continue;

}

swapt += swaptimes/2;

}

void mergesrt(int* a,int start,int end){

int mid = (start+end)/2;

if (start < end) {

mergesrt(a, start, mid);

mergesrt(a, mid+1, end);

merge(a,start,mid,end);

}

int main(){

int n = 0;

int seq[500005];

while (cin >> n && n) {

swapt = 0;

for (int i = 0; i < n; i++) {

scanf(" %d",&seq[i]);

}

mergesrt(seq, 0, n-1);

cout << swapt << endl;

}

return 0;

}

SXBK,总的交换次数会爆掉int。。。我他妈wa了一天

改造归并排序，保存交换次数就可以了

HDU 1969 Pie

January 20, 20152015-01-20hahaschoolLeave a comment

#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <vector>
#include <queue>
using namespace std;
bool cmp(int a,int b){
    return a>b;
}
int main(){
    int caseCnt = 0;
    scanf("%d",&caseCnt);
    for (int xxi = 1; xxi <= caseCnt; xxi++) {
        int n = 0,f= 0;
        double r[10005];
        cin >> n >> f;
        for (int i = 1; i <= n; i++) {
            scanf("%lf",&r[i-1]);
            r[i-1] *= r[i-1];
        }
        f++;
        sort(r, r+n, cmp);
        double high = r[0],low = 0;
        int rf;
        bool ans = false;
        double i = (high+low)/2;
        while (high - low > 0.0000001){
            ans = false;
            i = (high+low)/2;
            rf = f;
            for (int q = 1; q <= n; q++) {
                rf -= (int)(r[q-1]/i);
                if (rf <= 0) {
                    ans = true;
                    break;
                }
            }
            if (!ans) {
                high = i;
            }else{
                low = i;
            }
        }
        double pi = asin(1.0) * 2;
        printf("%.4lfn",i * pi);
    }
    return 0;
}

#include <cmath>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <string>

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <vector>

#include <queue>

using namespace std;

bool cmp(int a,int b){

return a>b;

}

int main(){

int caseCnt = 0;

scanf("%d",&caseCnt);

for (int xxi = 1; xxi <= caseCnt; xxi++) {

int n = 0,f= 0;

double r[10005];

cin >> n >> f;

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

scanf("%lf",&r[i-1]);

r[i-1] *= r[i-1];

}

f++;

sort(r, r+n, cmp);

double high = r[0],low = 0;

int rf;

bool ans = false;

double i = (high+low)/2;

while (high - low > 0.0000001){

ans = false;

i = (high+low)/2;

rf = f;

for (int q = 1; q <= n; q++) {

rf -= (int)(r[q-1]/i);

if (rf <= 0) {

ans = true;

break;

}

if (!ans) {

high = i;

}else{

low = i;

}

double pi = asin(1.0) * 2;

printf("%.4lfn",i * pi);

}

return 0;

}

二分的，然后要注意自已还得吃呢，别都给人家了，所以f要＋1，然后在hdu上，用long double一定wa，不用想，改成double就好了。

就这样。

POJ 2503 Babelfish

January 20, 20152015-01-20hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <stack>

using namespace std;

map<string,string> dict;

int main(){
    ios_base::sync_with_stdio(false);
    string toProc;
    while (getline(cin,toProc) && toProc.size()) {
        string eng,dia;
        int i = 0;
        for (; i < toProc.size(); i++) {
            if (toProc[i] == ' ') {
                i++;
                break;
            }
            eng += toProc[i];
        }
        for (; i < toProc.size(); i++) {
            dia += toProc[i];
        }
        dict[dia] = eng;
    }
    while (cin >> toProc) {
        string toOut = dict[toProc];
        if (toOut.size()) {
            cout << toOut << endl;
        }else{
            cout << "eh" << endl;
        }

    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <stack>

using namespace std;

map<string,string> dict;

int main(){

ios_base::sync_with_stdio(false);

string toProc;

while (getline(cin,toProc) && toProc.size()) {

string eng,dia;

int i = 0;

for (; i < toProc.size(); i++) {

if (toProc[i] == ' ') {

i++;

break;

}

eng += toProc[i];

}

for (; i < toProc.size(); i++) {

dia += toProc[i];

}

dict[dia] = eng;

}

while (cin >> toProc) {

string toOut = dict[toProc];

if (toOut.size()) {

cout << toOut << endl;

}else{

cout << "eh" << endl;

}

return 0;

}

这个是拿map水过去的版本，其实应该自己手写一个的。。。