当前位置：网站首页>2020ccpc Qinhuangdao exam results (ruler)

2020ccpc Qinhuangdao exam results (ruler)

2022-07-18 01:38:00 【51CTO】

7-5 Exam Results

Professor Alex is preparing an exam for his students now.

There will be n students participating in this exam. If student i has a good mindset, he/she will perform well and get ai points. Otherwise, he/she will get bi points. So it is impossible to predict the exam results. Assume the highest score of these students is x points. The students with a score of no less than x⋅p% will pass the exam.
Alex needs to know what is the maximum number of students who can pass the exam in all situations. Can you answer his question?

Input
The first line of the input gives the number of test cases, T (1≤T≤5×103). T test cases follow.
For each test case, the first line contains two integers n (1≤n≤2×105) and p (1≤p≤100), where n is the number of students and p% is the ratio.
Each of the following n lines contains two integers ai,bi (1≤bi≤ai≤109), representing the scores of student i.
The sum of n in all test cases doesn’t exceed 5×105.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1), and y is the maximum number of students.
Sample Input

Sample Output

       
       Case #1: 2
       
Case #2: 4
      
1.
2.

The question
Give you A student , Each student has two grades , You can choose one of these two grades , How many people let you pass the exam ? The condition for passing is : Go here n Multiply the highest score of students by %p This is the passing line . Less than this score, you will fail .

Ideas :
We can find from the meaning of the question that if we reduce the maximum pass line, the attendance will be reduced , Similarly, we should also improve the maximum passing line , So the difficulty we need to solve is here . First let's look at , The condition is that it will be pulled out Students, this is certain , Then choose the one with the highest score , We can give this first Overall ranking of grades , So we can easily find the biggest , Then I wonder how to know which score this student chooses or whether this student participates in the score selection , Then we need to mark , use The array marks whether the current point is all pop fall .
Take with ruler : Because we are entering elements on one side , Enter the largest one , The one who comes out with another element is unqualified ( Think the maximum score is improving , The passing score is also improved ) This is a typical ruler .
Look at the code specifically .
This question is inexplicably stuck long long I don't know why .

Code

       
       #include <stack>
       
       #include <map>
       
       #include <queue>
       
       #include <string>
       
       #include<iostream>
       
       #include<stdio.h>
       
       #include<string.h>
       
       #include <algorithm>
       
       #include <math.h>
       
       typedef 
       
       long 
       
       long 
       
       ll;
       
       typedef 
       
       unsigned 
       
       long 
       
       long 
       
       ull;
       
       using 
       
       namespace 
       
       std;
       
       typedef 
       
       pair
       
       <
       
       ll, 
       
       ll
       
       > 
       
       pii;
       
       #define
       
       #define
       
       #define
       
       #define
       
       #define
       
       const 
       
       int 
       
       maxn 
       
       = 
       
       5e5 
       
       + 
       
       10;
       
       #define
       
       #define
       
       #define
       
       const 
       
       int 
       
       mod 
       
       = 
       
       1e9 
       
       + 
       
       7;
       
       struct 
       
       node
       
{
       
       ll 
       
       val,
       
       id;
       
} 
       
       q[
       
       maxn];
       
       bool 
       
       cmp(
       
       node 
       
       a,
       
       node 
       
       b)
       
{
       
       return 
       
       a.
       
       val
       
       <
       
       b.
       
       val;
       
}
       
       ll 
       
       vis[
       
       maxn];
       
       ll 
       
       n,
       
       p,
       
       cnt;
       
       int 
       
       main()
       
{
       
       ll 
       
       t,
       
       T
       
       =
       
       0;
       
       cin
       
       >>
       
       t;
       
       while(
       
       t
       
       --)
       
    {
       
       cnt
       
       =
       
       0;
       
       scanf(
       
       "%lld%lld",
       
       &
       
       n,
       
       &
       
       p);
       
       for(
       
       int 
       
       i
       
       =
       
       1; 
       
       i
       
       <=
       
       n; 
       
       i
       
       ++)
       
        {
       
       ll 
       
       a,
       
       b;
       
       scanf(
       
       "%lld%lld",
       
       &
       
       a,
       
       &
       
       b);
       
       q[
       
       ++
       
       cnt].
       
       val
       
       = 
       
       a;
       
       /// Mark the following discretization 
       
       q[
       
       cnt].
       
       id
       
       =
       
       i;
       
       q[
       
       ++
       
       cnt].
       
       val
       
       = 
       
       b;
       
       /// Mark the following discretization 
       
       q[
       
       cnt].
       
       id
       
       =
       
       i;
       
       vis[
       
       i]
       
       =
       
       0;
       
        }
       
       sort(
       
       q
       
       +
       
       1,
       
       q
       
       +
       
       1
       
       +
       
       cnt,
       
       cmp);
       
       /// Sort , Sort by grade 
       
       ll 
       
       top
       
       =
       
       1,
       
       res
       
       =
       
       0;
       
       ///top Subscript indicating the first pass element  res The following table indicates the highest score 
       
       ll 
       
       now
       
       =
       
       0;
       
       /// Now it means the number of people who have passed 
       
       while(
       
       now
       
       !=
       
       n)
       
       /// Let's preprocess it first , Find the first satisfaction   contain n Subscript of students 
       
        {
       
       res
       
       ++;
       
       if(
       
       vis[
       
       q[
       
       res].
       
       id]
       
       ==
       
       0)
       
       /// It didn't show up   The number of +1
       
            {
       
       now
       
       ++;
       
            }
       
       vis[
       
       q[
       
       res].
       
       id]
       
       ++;
       
       /// Mark how many times the current student appears 
       
        }
       
       now
       
       --;
       
       /// I thought it would be  res++  So first put this pop fall 
       
       ll 
       
       ans
       
       =
       
       0;
       
       vis[
       
       q[
       
       res].
       
       id]
       
       --;
       
       res
       
       --;
       
       while(
       
       res
       
       <
       
       cnt)
       
        {
       
       res
       
       ++;
       
       /// Move back one position 
       
       if(
       
       vis[
       
       q[
       
       res].
       
       id]
       
       ==
       
       0)
       
       /// Not in the pass mark   How many people ++
       
       now
       
       ++;
       
       vis[
       
       q[
       
       res].
       
       id]
       
       ++;
       
       while(
       
       q[
       
       top].
       
       val
       
       *
       
       100
       
       <
       
       q[
       
       res].
       
       val
       
       *
       
       p)
       
       ///  Pass points are raised to plateau. Those who pass fail 
       
            {
       
       if(
       
       vis[
       
       q[
       
       top].
       
       id]
       
       ==
       
       1)
       
       /// This is the only point   Just take this person from the pass list pop fall 
       
                {
       
       now
       
       --;
       
                }
       
       vis[
       
       q[
       
       top].
       
       id]
       
       --;
       
       top
       
       ++;
       
       /// The passing subscript moves back 
       
            }
       
       ans
       
       =
       
       max(
       
       now,
       
       ans);
       
       /// Find the biggest 
       
        }
       
       printf(
       
       "Case #%lld: %lld\n",
       
       ++
       
       T,
       
       ans);
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/199/202207151024258937.html

当前位置：网站首页>2020ccpc Qinhuangdao exam results (ruler)

2020ccpc Qinhuangdao exam results (ruler)

7-5 Exam Results

边栏推荐

猜你喜欢

随机推荐