| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:数组越界判断忘记减1了,WA了3次, 附代码In Reply To:数组越界判断忘记减1了,WA了3次 Posted by:KatrineYang at 2016-05-26 01:01:19 > 真是没谁了
//============================================================================
// Name : main1018.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <vector>
#include <cstdlib>
#include <stdio.h>
using namespace std;
int mini(int a, int b){
if(a < b) return a;
return b;
}
class bw_pr{
public:
int bw;
int pr;
bw_pr(int b, int p): bw(b), pr(p){
}
bw_pr(): bw(0), pr(0){
}
};
int partion(bw_pr* array, int p, int r) {
bw_pr x = array[r];
int i = p - 1;//注意这点,把i设成负值,然后作为移动的标志
int j;
for (j = p; j < r; j++) {
if (array[j].bw > x.bw) {
i++;
bw_pr temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
bw_pr temp = array[j];
array[j] = array[i + 1];
array[i + 1] = temp;
return i+1;//返回的应该是交换后的哨兵的位置
}
//递归解决每个划分后的小
void quickSort(bw_pr* array, int p, int r) {
if (p < r) {
int q = partion(array, p, r);
quickSort(array, p, q - 1);
quickSort(array, q + 1, r);
}
}
int main() {
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
int testcase;
cin >> testcase;
for(int ii = 0; ii < testcase; ii++){
int device;
cin >> device;
vector<bw_pr> info[100];
for(int jj = 0; jj < device; jj++){
int manu;
cin >> manu;
bw_pr temp[100];
for(int i = 0; i < manu; i++){
int bw, pr;
cin >> bw >> pr;
//bw_pr* temp_ = new bw_pr(bw, pr);
temp[i].bw = bw;
temp[i].pr = pr;
}
quickSort(temp, 0, manu-1);
int pr = 2147483647;
for(int i = 0; i < manu; i++){
if(temp[i].pr < pr){
pr = temp[i].pr;
info[jj].push_back(temp[i]);
}
}
//for(int i = 0; i < info[jj].size(); i++) cout << info[jj][i].bw << " " <<
//info[jj][i].pr << endl;
//delete [] temp;
}
vector<bw_pr> res[2];
res[0].push_back(bw_pr(2147483647, 0));
for(int i = 0; i < device; i++){
vector<bw_pr>& from = res[i%2], &to = res[(i+1)%2], &ref = info[i];
to.clear();
//下面合并from和ref中的内容并放入to中
int fromSize = from.size(), refSize = ref.size();
int fromIndex = 0, refIndex = 0;
int targetBw = mini(from[fromIndex].bw, ref[refIndex].bw);
while(1){
//cout << targetBw << endl;
//找到最后一个大于等于targetBw的
if(from[fromIndex].bw > targetBw){
while(1){
fromIndex++;
if(fromIndex == fromSize || from[fromIndex].bw < targetBw) break;
}
fromIndex--;
}
if(ref[refIndex].bw > targetBw){
while(1){
refIndex++;
if(refIndex == refSize || ref[refIndex].bw < targetBw) break;
}
refIndex--;
}
to.push_back(bw_pr(targetBw, from[fromIndex].pr + ref[refIndex].pr));
//将结果放入目标中
if(fromIndex < fromSize - 1) fromIndex++;
if(refIndex < refSize - 1) refIndex++;
int newtargetBw = mini(from[fromIndex].bw, ref[refIndex].bw);
if(newtargetBw == targetBw) break;
targetBw = newtargetBw;
}
}
vector<bw_pr>& po = res[device%2];
//for(int i = 0; i < po.size(); i++) cout << po[i].bw << " " <<
//po[i].pr << endl;
double b_p = 0;
int size = po.size();
for(int i = 0; i < size; i++){
double newb_p = po[i].bw * 1.0 / po[i].pr;
if(newb_p > b_p) b_p = newb_p;
}
printf("%.3f\n", b_p);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator