pku 1634 Who's the boss? stl排序+二分查找

╰半夏微凉° 2022-08-09 14:53 78阅读 0赞

#include #include #include using namespace std; struct Person { int id; int salary; int height; int bossId; int sub; }; bool func1(const Person& p1, const Person& p2) { return p1.salary < p2.salary; } bool func2(const Person& p1, const Person& p2) { return p1.id < p2.id; } Person p[30000]; int search(int low, int high, int id) { while(low <= high) { int mid = (low+high)>>1; if(p[mid].id == id) return mid; else if(id < p[mid].id) high = mid-1; else low = mid+1; } return -1; } int main() { int cnt; int m, q; scanf(“%d”, &cnt); while(cnt—) { memset(p, 0, sizeof(p)); scanf(“%d%d”, &m, &q); for (int i = 0; i < m; ++i) scanf(“%d%d%d”, &p[i].id, &p[i].salary, &p[i].height); sort(p, p+m, func1); for (int i = 0; i < m; ++i) { for(int j = i+1; j < m; ++j) if(p[i].height <= p[j].height) //这儿搞成了<,郁闷了好久,晕… { p[i].bossId = p[j].id; p[j].sub = p[j].sub + p[i].sub + 1; break; } } sort(p, p+m, func2); int queryid; for (int i = 0; i < q; ++i) { scanf(“%d”, &queryid); int index = search(0, m-1, queryid); printf(“%d %d/n”, p[index].bossId, p[index].sub); } } return 0; }

发表评论

表情：
评论列表 （有 0 条评论，78人围观）

还没有评论，来说两句吧...

相关阅读

    相关 冒泡排序与二分查找

    冒泡排序： 冒泡排序的核心思想是用第一个数依次与以后的数比较，如果有比它大或者比它小的就与它交换位置，那么第一个得到的数就是最大或者最小的；同理用第二个数再执行依次，，，依次

    Bertha 。Bertha 。/ 0 赞/ 276 阅读

    相关 JAVA 排序与二分查找

    排序与二分查找 冒泡排序 排序思想：从前往后将相邻的两个元素进行比较，则第一次比较完成后，最后一个元素一定是数值最大的。依次重复，每一轮比较就会将剩余元素中的最大一

    谁践踏了优雅谁践踏了优雅/ 0 赞/ 319 阅读