POJ-3664的解题思路有哪些？
- 内容介绍
- 文章标签
- 相关推荐
本文共计647个文字，预计阅读时间需要3分钟。
当然可以，请您提供需要改写的原文，我会帮您进行简化并控制在100字以内。
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define COW_NUM 50000
class cow_vote {
public:
int index;
long Avote;
long Bvote;
void operator=(const cow_vote & p) {
index = p.index;
Avote = p.Avote;
Bvote = p.Bvote;
}
};
// typedef struct cow_vote cow_vote;
cow_vote CowVoteInfo[COW_NUM];
template <typename T>
class Less{
public:
char operator()(const T & p1, const T & p2) {
return p1 < p2;
}
};
template <typename T>
class More{
public:
char operator()(const T & p1, const T & p2) {
return p1 > p2;
}
};
template <typename T>
class commonExchanger{
public:
void operator()(T & p1, T & p2) {
T tmp = p1;
p1 = p2;
p2 = tmp;
}
};
class MoreVote {
public:
virtual char operator()(const cow_vote & p1, const cow_vote & p2) = 0;
};
class MoreAVote : public MoreVote{
public:
virtual char operator()(const cow_vote & p1, const cow_vote & p2) {
return p1.Avote > p2.Avote;
}
};
class MoreBVote : public MoreVote{
public:
virtual char operator()(const cow_vote & p1, const cow_vote & p2) {
return p1.Bvote > p2.Bvote;
}
};
class CowExchanger {
public:
void operator()(cow_vote & p1, cow_vote & p2) {
cow_vote tmp = p1;
p1 = p2;
p2 = tmp;
}
};
template <typename T, class C, class E>
class QuickSortor {
private:
C * mCmp;
T * mArray;
int mArrayLength;
E mExchanger;
// P mPrinter;
int partition(int begin, int end) {
T partitionValue = mArray[end];
int lastLessPos = begin - 1;
int currentCheckPos = begin;
for (; currentCheckPos <= end-1; currentCheckPos++) {
if ((*mCmp)(mArray[currentCheckPos], partitionValue)) {
// T tmp = mArray[lastLessPos+1];
// mArray[lastLessPos+1] = mArray[currentCheckPos];
// mArray[currentCheckPos] = tmp;
mExchanger(mArray[lastLessPos+1], mArray[currentCheckPos]);
lastLessPos++;
}
}
// T tmp = mArray[end];
// mArray[end] = mArray[lastLessPos+1];
// mArray[lastLessPos+1] = tmp;
mExchanger(mArray[end], mArray[lastLessPos+1]);
return lastLessPos+1;
}
void __sort(int begin, int end) {
if (begin < end) {
int partitionPos = partition(begin, end);
__sort(begin, partitionPos-1);
__sort(partitionPos+1, end);
}
}
public:
QuickSortor(T * array, C * cmp, int arrayLength, E exchanger): mCmp(cmp), mArray(array),
mArrayLength(arrayLength), mExchanger(exchanger) {
}
void reset() {
mArray = NULL;
mArrayLength = 0;
}
void sort() {
if (mArray && mArrayLength) {
__sort(0, mArrayLength-1);
}
}
};
// int test() {
// // int testArray[] = {100,223,9,-8,1,18,36,77,36,77, 89, 0, 1, 8, 6};
// int testArray[] = {100,223,9,48,1,18,39,76,36,77, 89, 0, 3, 8, 6};
// Less<int> lessCmp;
// commonExchanger<int> exchanger;
// QuickSortor<int, Less<int>, commonExchanger<int> >
// Qsortor(testArray, lessCmp, sizeof(testArray)/sizeof(int), exchanger);
// Qsortor.sort();
// for (int i = 0; i < sizeof(testArray)/sizeof(int); i++) {
// printf("%d ", testArray[i]);
// }
// printf("\n");
// }
void getPresident(int N, int K) {
MoreVote * A = new MoreAVote();
MoreVote * B = new MoreBVote();
CowExchanger cow_exchanger;
QuickSortor<cow_vote, MoreVote, CowExchanger> QsortorRound1(CowVoteInfo, A, N, cow_exchanger);
QsortorRound1.sort();
QuickSortor<cow_vote, MoreVote, CowExchanger> QsortorRound2(CowVoteInfo, B, K, cow_exchanger);
QsortorRound2.sort();
// for (int i = 0; i < N; i++) {
// printf("%ld ",CowVoteInfo[i].Avote);
// }
printf("%d\n", CowVoteInfo[0].index);
}
int main() {
// test();
int N;
int K;
scanf("%d %d", &N, &K);
memset(CowVoteInfo, 0, sizeof(CowVoteInfo));
for (int i = 0; i < N; i++) {
scanf("%ld %ld", &(CowVoteInfo[i].Avote), &(CowVoteInfo[i].Bvote));
CowVoteInfo[i].index = i+1;
}
getPresident(N, K);
}
952K 110MS G++
水题，纯粹为了练快排解的，其实堆排应该更合适，毕竟round1只需要得到前K大的即可.
顺便练了下模版，虚函数和封包。
算导的总结果然精辟，一次AC。
本文共计647个文字，预计阅读时间需要3分钟。
当然可以，请您提供需要改写的原文，我会帮您进行简化并控制在100字以内。
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define COW_NUM 50000
class cow_vote {
public:
int index;
long Avote;
long Bvote;
void operator=(const cow_vote & p) {
index = p.index;
Avote = p.Avote;
Bvote = p.Bvote;
}
};
// typedef struct cow_vote cow_vote;
cow_vote CowVoteInfo[COW_NUM];
template <typename T>
class Less{
public:
char operator()(const T & p1, const T & p2) {
return p1 < p2;
}
};
template <typename T>
class More{
public:
char operator()(const T & p1, const T & p2) {
return p1 > p2;
}
};
template <typename T>
class commonExchanger{
public:
void operator()(T & p1, T & p2) {
T tmp = p1;
p1 = p2;
p2 = tmp;
}
};
class MoreVote {
public:
virtual char operator()(const cow_vote & p1, const cow_vote & p2) = 0;
};
class MoreAVote : public MoreVote{
public:
virtual char operator()(const cow_vote & p1, const cow_vote & p2) {
return p1.Avote > p2.Avote;
}
};
class MoreBVote : public MoreVote{
public:
virtual char operator()(const cow_vote & p1, const cow_vote & p2) {
return p1.Bvote > p2.Bvote;
}
};
class CowExchanger {
public:
void operator()(cow_vote & p1, cow_vote & p2) {
cow_vote tmp = p1;
p1 = p2;
p2 = tmp;
}
};
template <typename T, class C, class E>
class QuickSortor {
private:
C * mCmp;
T * mArray;
int mArrayLength;
E mExchanger;
// P mPrinter;
int partition(int begin, int end) {
T partitionValue = mArray[end];
int lastLessPos = begin - 1;
int currentCheckPos = begin;
for (; currentCheckPos <= end-1; currentCheckPos++) {
if ((*mCmp)(mArray[currentCheckPos], partitionValue)) {
// T tmp = mArray[lastLessPos+1];
// mArray[lastLessPos+1] = mArray[currentCheckPos];
// mArray[currentCheckPos] = tmp;
mExchanger(mArray[lastLessPos+1], mArray[currentCheckPos]);
lastLessPos++;
}
}
// T tmp = mArray[end];
// mArray[end] = mArray[lastLessPos+1];
// mArray[lastLessPos+1] = tmp;
mExchanger(mArray[end], mArray[lastLessPos+1]);
return lastLessPos+1;
}
void __sort(int begin, int end) {
if (begin < end) {
int partitionPos = partition(begin, end);
__sort(begin, partitionPos-1);
__sort(partitionPos+1, end);
}
}
public:
QuickSortor(T * array, C * cmp, int arrayLength, E exchanger): mCmp(cmp), mArray(array),
mArrayLength(arrayLength), mExchanger(exchanger) {
}
void reset() {
mArray = NULL;
mArrayLength = 0;
}
void sort() {
if (mArray && mArrayLength) {
__sort(0, mArrayLength-1);
}
}
};
// int test() {
// // int testArray[] = {100,223,9,-8,1,18,36,77,36,77, 89, 0, 1, 8, 6};
// int testArray[] = {100,223,9,48,1,18,39,76,36,77, 89, 0, 3, 8, 6};
// Less<int> lessCmp;
// commonExchanger<int> exchanger;
// QuickSortor<int, Less<int>, commonExchanger<int> >
// Qsortor(testArray, lessCmp, sizeof(testArray)/sizeof(int), exchanger);
// Qsortor.sort();
// for (int i = 0; i < sizeof(testArray)/sizeof(int); i++) {
// printf("%d ", testArray[i]);
// }
// printf("\n");
// }
void getPresident(int N, int K) {
MoreVote * A = new MoreAVote();
MoreVote * B = new MoreBVote();
CowExchanger cow_exchanger;
QuickSortor<cow_vote, MoreVote, CowExchanger> QsortorRound1(CowVoteInfo, A, N, cow_exchanger);
QsortorRound1.sort();
QuickSortor<cow_vote, MoreVote, CowExchanger> QsortorRound2(CowVoteInfo, B, K, cow_exchanger);
QsortorRound2.sort();
// for (int i = 0; i < N; i++) {
// printf("%ld ",CowVoteInfo[i].Avote);
// }
printf("%d\n", CowVoteInfo[0].index);
}
int main() {
// test();
int N;
int K;
scanf("%d %d", &N, &K);
memset(CowVoteInfo, 0, sizeof(CowVoteInfo));
for (int i = 0; i < N; i++) {
scanf("%ld %ld", &(CowVoteInfo[i].Avote), &(CowVoteInfo[i].Bvote));
CowVoteInfo[i].index = i+1;
}
getPresident(N, K);
}
952K 110MS G++
水题，纯粹为了练快排解的，其实堆排应该更合适，毕竟round1只需要得到前K大的即可.
顺便练了下模版，虚函数和封包。
算导的总结果然精辟，一次AC。