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